POJ 3450 Corporate Identity （KMP+暴搞）

题意：

给定N个字符串，寻找最长的公共字串，如果长度相同，则输出字典序最小的那个。

找其中一个字符串，枚举它的所有的字串，然后，逐个kmp比较.......相当暴力，可二分优化。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
char str[4111][221];
int next[222];

void getnext(char *t) {
    int i=0,j=-1;
    int len = strlen(t);
    next[0] = -1;
    while(i < len) {
        if(t[i] == t[j] || j == -1) {
            i ++;
            j ++;
            next[i] = j;
        } else j = next[j];
    }
}

int kmp(char *s,char *t) {
    int lens = strlen(s);
    int lena = strlen(t);
    int i=0,j=0;
    while(i < lens && j < lena) {
        if(s[i] == t[j] || j == -1) {
            i++;
            j++;
        } else j = next[j];
    }
    if(j < lena) return -1;
    return i - lena;
}

int main() {
    int n,len;
    while(cin >> n && n) {
        char tmp[222];
        int minn = 111111;
        for(int i=0; i<n; i++) {
            scanf("%s",str[i]);
            len = strlen(str[i]);
            if(minn > len) { 
                minn= len;
                strcpy(tmp,str[i]);
            }
        }
        len = strlen(tmp);
        char p[222];
        char final[222] = {0};
        int ans = 0;
        for(int i=1; i<=len; i++) { //枚举所有的字串
            int cnt;
            for(int j=0; j + i<=len; j++) {
                cnt = 0;
                strncpy(p,tmp+j,i);
                p[i] = '';

                getnext(p);
                for(int k=0; k<n; k++) { //逐个比较
                    if(kmp(str[k],p) != -1) {
                        cnt ++;
                    }
                    else break;
                }
                if(cnt == n) {
                    ans++;

                    if(strlen(final) < strlen(p)) strcpy(final,p);
                    else if(strcmp(final,p) > 0) strcpy(final,p);

                }
            }
        }
        if(ans == 0) printf("IDENTITY LOST
");
        else {
            printf("%s
",final);
        }
    }
    return 0;
}