题目：从一个字符串找到最长的重复字符串并返回第一个字符的位置。
思路一：暴力，不做太多解释。
思路二：根据字符串的查找理所当然想到KMP，KMP的next数组，next[i]=k，从该字符串头结点开始的后k个结点与i结点往前k个字符串相同，很明显了。然后遍历再调整一下Getnext函数让其返回此次计算的最大值就行了。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> #include <map> #include <queue> #include <vector> #define PI acos(-1) #define INF 1e18 #define inf 1e9 #define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define Si(i) scanf("%d",&i) #define Pi(i) printf("%d\n",i); #define ElemType int using namespace std ; typedef long long ll; typedef unsigned long long ull; const int _max = 10005; const ll mod = 1e9+7; char str[_max]; int next[_max]; int getNext(char *str,int *next){ int len=strlen(str); int index=0; int k=-1; next[0]=k; int max=0; while(index<len){ if(k == -1 || str[index] == str[k]){ k++; index++; next[index]=k; if(k>max) max = k; } else k=next[k]; } for(int i = 0 ; i < len ; i++) cout<<next[i]<<' '; cout<<endl; return max; } int main(){ while(cin>>str){ int max=0; int nextMax; int maxIndex; int len=strlen(str); for(int index=0;index<len-1;index++){ nextMax=getNext(str+index,next); if(nextMax>max){ max=nextMax; maxIndex=index; } } cout<<maxIndex<<endl; for(int i = 0 ; i < max ; i++) cout<<str[maxIndex+i]; cout<<endl; } return 0; }
