POJ 3080

也许是不甘心深藏的梦想，也许是痛恨自己的懦弱。
不管怎么样，接下来请笃定认真走下去吧

本题利用暴力也是可以做的，不过是在练习KMP的思路，所以，还是利用了KMP进行优化。
中间出过一个很久的bug，原来是初始化没有做好，还是编程习惯的问题吧。

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <stack>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxm= 12;
const int maxl= 65;
const int l= 60;

char s[maxm][maxl];
int kn[maxl][maxl][maxl];

void PreKmp(char *x, int l ,int *nxt)
{
	int i= 0, j= -1;
	nxt[0]= -1;

	while (i< l){
		while (j> -1 && x[i]!= x[j]){
			j= nxt[j];
		}
		++i;
		++j;

		if (x[i]== x[j]){
			nxt[i]= nxt[j];
		}
		else{
			nxt[i]= j;
		}
	}
}
int main()
{
	int n;
	scanf("%d", &n);

	while (n--){
		int m, as= -1, al= -1;
		scanf("%d", &m);

		for (int i= 0; i< m; ++i){
			scanf("%s\n", s[i]);
		}	

		for (int k= 3; k<= l; ++k){
			int j= k;
			for (int i= 0; j<= l; ++i, ++j){
				char c= s[0][j];
				s[0][j]= ‘\0‘;
				PreKmp(s[0]+i, k, kn[i][k]);
				s[0][j]= c;
			}
		}

		for (int k= 3; k<= l ;++k){
			int j= k;
			for (int i= 0; j<= l; ++i, ++j){
				int flag= 1;
				for (int p= 1; p< m && flag; ++p){
					int x= 0, y= 0;
					while (y< k && x< l){
						while (y> -1 && s[p][x]!= s[0][i+y]){
							y= kn[i][k][y];
						}
						++x;
						++y;
					}
					if (y< k){
						flag= 0;
					}
				}

				if (flag){
					if (k> al){
						as= i;
						al= k;
					}
					else if (strncmp(s[0]+i, s[0]+as, al) < 0){
						as= i;
					}
				}
			}
		}

		if (al< 3){
			printf("no significant commonalities\n");
		}
		else{
			s[0][as+al]= ‘\0‘;
			printf("%s\n", s[0]+as);
		}
	}
	return 0;
}

POJ 3080

原文：https://www.cnblogs.com/Idi0t-N3/p/14583956.html