2015
09-17

# Theme Section

It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a ‘theme section’. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of ‘EAEBE’, where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters ‘a’ – ‘z’.

To get well prepared for the festival, the hosts want to know the maximum possible length of the theme section of each song. Can you help us?

The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6.

The integer N in the first line denotes the total number of songs in the festival. Each of the following N lines consists of one string, indicating the notes of the i-th (1 <= i <= N) song. The length of the string will not exceed 10^6.

5
xy
abc
aaa
aaaaba
aaxoaaaaa

0
0
1
1
2

next[i]表示以i为开始位置的子串与整个串的前缀最长匹配到多少长度

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 1111111
#define MAXM 211111
#define PI acos(-1.0)
#define eps 1e-8
#define INF 1e10
using namespace std;
int A[MAXN], B[MAXN];
char sa[MAXN];
void preExKmp(char x[],int m,int A[]){
int ind=0,k=1;
A[0]=m;
while (ind + 1 < m && x[ind+1]==x[ind]) ++ind;
A[1]=ind;
for (int i=2;i<m;++i){
if (i<=k+A[k]-1 && A[i-k]+i<k+A[k])
A[i]=A[i-k];
else{
ind=max(0,k+A[k]-i);
while (ind + i < m && x[ind+i]==x[ind]) ++ind;
A[i]=ind,k=i;
}
}
}
void exKmp(char x[],int m , char y[],int n,int A[],int B[]){
preExKmp(x,m,A);
int ind=0,k=0;
while (ind<n && ind<m && x[ind]==y[ind]) ind++;
B[0]=ind;
for (int i=1;i<n;++i){
if (i < k+B[k]-1 && A[i-k]+i<k+B[k])
B[i]=A[i-k];
else{
ind = max(0,k+B[k]-i);
while (ind +i<n && ind<m && y[ind+i]==x[ind]) ++ind;
B[i]=ind;k=i;
}
}
}

int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%s", sa);
int len = strlen(sa);
preExKmp(sa, len, A);
int ans = 0;
int lst = len - len / 3, mxlen;
for(int i = 0; i < len; i++)
{
mxlen = min(i, A[i]);
mxlen = min(mxlen, (len - i) / 2);
ans = max(ans, mxlen);
}
int res = 0;
for(int i = lst; i < len; i++)
{
if(A[i] + i != len) continue;
if(ans >= A[i])
{
res = A[i];
break;
}
}
printf("%d\n", res);
}
return 0;
}


1. 谢谢，我一直在找一部漫画，记忆里叫什么”风”"剑”"雷”的，里面还有什么要背叛人的霸王丸的漫画，原来是《剑风传奇》，可算找到了

2. 9.15我跟他分手了，到10.6就整整三年的感情，我也搞不懂自己，内心的不安分，昨天，他发信息，如果我考上工程师，你会回来吗？我说，不知道，可能吧，这算是什么情况，自己都搞不懂

3. ᴣᴣᴣᴣᴣᴣᴣᴣᴣ穿着丝袜干ᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣ撕破丝袜ᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣ李思思丝袜ᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣ空气丝袜ᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣ白色丝袜的诱惑ᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣᴣ丝袜家ᴣᴣᴣᴣᴣᴣᴣᴣᴣmeitui1.com