正好练习写一下后缀数组。
#include<iostream> #include<iterator> #include<vector> #include<algorithm> using namespace std; struct node { char* s; int start; node(char* ss,int t):s(ss),start(t){} bool operator<(const node& oth)const { return strcmp(s,oth.s)<=0; } }; void suffixArray(char* s) { vector<node> sa; for(int i=0;s[i]!='\0';i++) sa.push_back(node(s+i,i)); sort(sa.begin(),sa.end()); vector<int> rank(sa.size()); for(int i=0;i<sa.size();i++) rank[sa[i].start]=i; vector<int> height(sa.size()); int k=0; for(int i=0;i<rank.size();i++) { if(rank[i]==0) continue; int j=sa[rank[i]-1].start; k=max(k-1,0); for(;s[i+k]==s[j+k];k++) ; height[rank[i]]=k; } //最长重复子串 cout<< "最长重复子串: " <<endl; cout << *max_element(height.begin(),height.end()) <<endl; cout <<"最长不重叠子串: " <<endl; int l =0,r=sa.size()-1; int ans=0; while(l<=r) { int mid=(l+r)>>1; int wLeft=0,wRight=0; int ok=0; while(wLeft<sa.size()) { if(wRight>=sa.size()||height[wRight]<mid) { wLeft=wRight; wRight++; } else { while(wRight<sa.size()&&height[wRight]>=mid) wRight++; int minH=sa[wLeft].start; int maxH=sa[wLeft].start; while(wLeft<wRight) { minH=min(minH,sa[wLeft].start); maxH=max(maxH,sa[wLeft].start); wLeft++; } if(maxH-minH>=mid) { ok=1; break; } } } if(ok) { ans=mid; l=mid+1; } else { r=mid-1; } } cout<<ans<<endl; } char st[100]; int main() { while(scanf("%s",st)) { suffixArray(st); cout<<endl; } }