注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj3080 Blue Jeans KMP+枚举  

2011-02-28 14:19:49|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://poj.org/problem?id=3080

不多说与poj3450 差不多,都是求几个字符串拥有的相同子串,并是最长的。不过这题要求子串长度不低于3,还有各个提供的字符串长度也都相等。

所以是把做过的poj3450稍微改下,很给力0ms通过。poj3080 Blue Jeans KMP+枚举 - 某年某月 - zxj015的博客

Source Code

Problem: 3080 User: 541780774
Memory: 708K Time: 0MS
Language: G++ Result: Accepted

Source Code

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
int next[65],n,T,minlen,tlen,samelen;
struct {
       char str[65];
       }r,s[11],t,ans;
void get_next()//求模式串的“next[]”值
{
     long i=0,j=-1;
     next[0]=-1;
     while(i<=tlen)
     {
       if(j==-1||t.str[i]==t.str[j])
         next[++i]=++j;
       else j=next[j];
     }
}
int kmp()
{
    int h,i,j,max,min=99999;
    for(h=1;h<T;h++)
    {
          i=0;j=0;max=0;
          while(i<samelen&&j<tlen)
         {
            if(j==-1||s[h].str[i]==t.str[j])
            {
              i++;j++;
              if(j>max)
                 max=j;
            }
            else
            {
                 if(j>max)//匹配串与某主串最长的匹配长度max;
                 max=j;
                 j=next[j];
            }
         }
        if(max<min) //该匹配串与所有的主串的匹配长度max中取最小min
          min=max;
    }
    return min;
}
main()
{
   long i,a,max,N;
   scanf("%d",&N);
   while(N--)
   {
      scanf("%d",&T);
      getchar();
      minlen=99999;
      max=2;
      for(i=0;i<T;i++)
         gets(s[i].str);
      samelen=strlen(s[0].str);
      for(i=0;i<samelen;i++)
      {
        strcpy(t.str,s[0].str+i);//枚举子串中所有拿去匹配的串
        tlen=strlen(t.str);
        get_next();
        a=kmp();
        if(a>max)
        {
           max=a;
           strncpy(ans.str,s[0].str+i,a);
           ans.str[a]='\0';
        }
        else if(a==max)   //如果两字符串长度相等,取小串的;取ASCII码值小的串
        {
           strncpy(r.str,s[0].str+i,a);
           r.str[a]='\0';
           if(strcmp(ans.str,r.str)>0)
             strcpy(ans.str,r.str);
        }
      }
      if(max<3)
          printf("no significant commonalities\n");
      else
          printf("%s\n",ans.str);
   }
   system("pause");
}

  评论这张
 
阅读(193)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018