BOJ 477. 新来的小妹妹

新来的小妹妹"/>

BOJ 477. 新来的小妹妹

题意：给出一个字符串，找出其中出现次数大于等于2次且最长的连续子串。出现的两次可以重叠。

思路：后缀数组

代码如下：

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>using namespace std;void radix(int * str, int *a, int *b, int n, int m){static int count[200000];memset(count,0,sizeof(count));for(int i = 0; i < n; ++i) ++count[str[a[i]]];for(int i = 1; i <= m; ++i) count[i] += count[i-1];for(int i = n -1; i >= 0; --i) b[--count[str[a[i]]]] = a[i];
}void suffix_array(int* str,int * sa, int n, int m)
{static int rank[200000],a[200000],b[200000];for(int i = 0; i < n; ++i) rank[i] =i;radix(str,rank,sa,n,m);rank[sa[0]] = 0;for(int i = 1; i < n; ++i)rank[sa[i]]= rank[sa[i-1]] +(str[sa[i]]!=str[sa[i-1]]);for(int i = 0; 1<<i< n; ++i){for(int j = 0; j < n; ++j){a[j] = rank[j]+1;b[j] = j + (1<<i) >=n? 0: rank[j + (1<<i)] + 1;sa[j] = j;}radix(b,sa,rank,n,n);radix(a,rank,sa,n,n);rank[sa[0]] = 0;for(int j = 1; j < n; ++j){rank[sa[j]] = rank[sa[j-1]] + (a[sa[j-1]] != a[sa[j]] || b[sa[j-1]] != b[sa[j]]);}}
}int duplicate_substr(string str)
{string rev;static int s[3000],sa[3000],rank[3000],h[3000];int n = str.length();copy(str.begin(),str.end(),s);suffix_array(s,sa,n,256);for(int i = 0 ; i < n; ++i)rank[sa[i]] = i;int k = 0;int ans1 =0,pos1 = 0;for(int i = 0; i < n; ++i){k = k==0? 0: k - 1;while(rank[i] > 0 && s[i + k] == s[sa[rank[i] - 1] + k]) ++k;h[rank[i]] = k;if(h[rank[i]] > ans1){ans1 = h[rank[i]];pos1 = i;}}return str.substr(pos1,ans1).length();
}int main(void)
{int T;string str;scanf("%d", &T);while(T--){cin>> str;cout<<duplicate_substr(str)<<'\n';}return 0;
}