POJ 3080 Blue Jeans KMP+暴力 - c++编程基础

题意：求m个串的最长公共子串。

每个串最长为60，枚举第一个子串的所有子串，然后在其他串KMP，找出最长的串。

我的枚举写的有点繁杂了...

其实想想，有几点可以优化的：

1.如果有很多连续的字符串，比如AAAAAA这样的，它的很多子串都是一样的，只要找一遍就行了，所以用map或hash判重下就能优化很多

2.它要求的是最长子串，所以枚举时可以剪掉很多长度比较短的.

我就优化了后面那条。

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        poj3080.cpp 
*  Create Date: 2013-11-29 09:29:58 
*  Descripton:  kmp, brute force  
*/  
  
#include   
#include   
  
const int MAXN = 70;  
  
char s[11][MAXN], sub[MAXN], ans[MAXN];  
int f[MAXN], alen;  
  
void getVal(char *P, int l) {  
    int i = 0, j = -1;  
    f[0] = -1;  
    while (i < l) {  
        if (j == -1 || P[i] == P[j]) {  
            i++, j++;  
            f[i] = j;  
        } else j = f[j];  
    }  
}  
  
bool kmp(char *T, char *P) {  
    int i = 0, j = 0;  
    int lt = strlen(T), lp = strlen(P);  
    getVal(P, lp);  
    while (i < lt) {  
        if (j == -1 || T[i] == P[j])  
            i++, j++;  
        else j = f[j];  
        if (j == lp) return true;  
    }  
    return false;  
}  
  
int main() {  
    int t, n;  
    scanf("%d", &t);  
    while (t--) {  
        ans[0] = '\0';  
        scanf("%d\n", &n);  
        for (int i = 0; i < n; i++)  
            gets(s[i]);  
        int len = strlen(s[0]);  
        alen = 0;  
        for (int i = 0; i <= len - 3; i++) {  
            int j, k = 0;  
            for (j = i; j < len; j++)  
                sub[k++] = s[0][j];  
            for (j = k; j >




= 3; j--) {  
                sub[j] = '\0';  
                if (j < alen) continue;  
                // deal  
                int t;  
                for (t = 1; t < n; t++)  
                    if (kmp(s[t], sub) == 0) break;  
                if (t == n) {  
                    if (alen < j || (alen == j && strcmp(ans, sub) > 0)) {  
                        strcpy(ans, sub);  
                        alen = j;  
                    }  
                }  
            }  
        }  
  
        if (ans[0] == '\0') puts("no significant commonalities");  
        else puts(ans);  
    }  
    return 0;  
}