两道相似KMP题

1.POJ 3450 Coporate Identity

这两题的解法都是枚举子串,然后匹配,像这种题目以后可以不用KMP来做,直接字符串自带的strstr函数搞定,如果字符串未出现,该函数返回NULL。

下面贴出其比较。

代码:(KMP版)(1360ms 888KB)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 4007 char ans[],str[];
char ss[N][],tt[];
int next[]; void getnext(char *ss)
{
int m = strlen(ss);
next[] = -;
int i = ,j = -;
while(i<m)
{
if(j == - || ss[i] == ss[j])
next[++i] = ++j;
else
j = next[j];
}
} int kmp(char *ss,char *tt)
{
int n = strlen(ss);
int m = strlen(tt);
getnext(tt);
int i = -,j = -;
while(i<n && j<m)
{
if(j == - || ss[i] == tt[j])
i++,j++;
else
j = next[j];
}
if(j == m)
return ;
return ;
} int main()
{
int n,i,len,j,k,lengh;
while(scanf("%d",&n)!=EOF && n)
{
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(!kmp(ss[j],str))
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0')
cout<<"IDENTITY LOST\n";
else
cout<<ans<<endl;
}
return ;
}

代码:(strstr函数版)(454ms 912KB)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 4007 char ans[],str[];
char ss[N][],tt[];
int main()
{
int n,i,len,j,k,lengh;
while(scanf("%d",&n)!=EOF && n)
{
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(strstr(ss[j],str) == NULL)
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0')
cout<<"IDENTITY LOST\n";
else
cout<<ans<<endl;
}
return ;
}

2.POJ 3080 Blue Jeans

代码:(KMP版)(32ms 684KB)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 4007 char ans[],str[];
char ss[][],tt[];
int next[]; void getnext(char *ss)
{
int m = strlen(ss);
next[] = -;
int i = ,j = -;
while(i<m)
{
if(j == - || ss[i] == ss[j])
next[++i] = ++j;
else
j = next[j];
}
} int kmp(char *ss,char *tt)
{
int n = strlen(ss);
int m = strlen(tt);
getnext(tt);
int i = -,j = -;
while(i<n && j<m)
{
if(j == - || ss[i] == tt[j])
i++,j++;
else
j = next[j];
}
if(j == m)
return ;
return ;
} int main()
{
int n,i,len,j,k,lengh,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(!kmp(ss[j],str))
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0' || strlen(ans) < )
cout<<"no significant commonalities\n";
else
cout<<ans<<endl;
}
return ;
}

代码:(strstr函数版)(0ms 700KB)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 4007 char ans[],str[];
char ss[][]; int main()
{
int n,i,len,j,k,lengh,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<n;i++)
scanf("%s",ss[i]);
lengh = strlen(ss[]);
ans[] = '\0';
for(len=;len<=lengh;len++) //枚举长度
{
for(i=;i<=lengh-len;i++) //枚举起点
{
for(k=,j=i;j<i+len;j++) //取出此字串
str[k++] = ss[][j];
str[k] = '\0';
for(j=;j<n;j++)
{
if(strstr(ss[j],str) == NULL)
break;
}
if(j == n)
{
if(strlen(ans) == len && strcmp(ans,str) > )
strcpy(ans,str);
if(strlen(ans) < len)
strcpy(ans,str);
}
}
}
if(ans[] == '\0' || strlen(ans) < )
cout<<"no significant commonalities\n";
else
cout<<ans<<endl;
}
return ;
}
上一篇:POJ 1815 Friendship(最大流最小割の字典序割点集)


下一篇:POJ 1815 Friendship(字典序最小的最小割)