首页 > 代码库 > POJ_3450_KMP

POJ_3450_KMP

2024-08-16 07:44:11   216人阅读

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

 

直接暴力枚举第一行的每一个字串，在下面的字符串中查找就行了，注意不符合就及时break。

然后试了一下strstr，发现效率是KMP的3-4倍。

还可以先排序找出最短的字符串，然后暴力，但是sort好像不能对char的二维数组排序，只能用string，string的字符串处理的函数都还没怎么看，就懒得搞了。

 

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;char a[4005][205];int n;bool cmp(char *x,char *y){    return strlen(x) < strlen(y);}int main(){    while(scanf("%d",&n) && n)    {        for(int i = 1;i <= n;i++)    scanf("%s",a[i]);        int len = strlen(a[1]);        char t[205],ans[205] = "";        for(int i = 0;i < len;i++)        {            int cnt = 0;            for(int j = i;j < len;j++)            {                t[cnt++] = a[1][j];                t[cnt] = 0;                int flag = 1;                for(int k = 2;k <= n;k++)                {                    if(!strstr(a[k],t))                    {                        flag = 0;                        break;                    }                }                if(flag)                {                    if(strlen(t) > strlen(ans) || strlen(t) == strlen(ans) && strcmp(t,ans) < 0)                    {                        memcpy(ans,t,sizeof(t));                    }                }            }        }        if(strlen(ans) == 0)    printf("IDENTITY LOST\n");        else    puts(ans);    }    return 0;}

 

POJ_3450_KMP


联系
我们