NPSC補完計劃
NPSC國中組 => NPSC2015國中組初賽 => 主題作者是: rscpp 於 十二月 09, 2015, 11:57:32 pm
-
// 30組、每組一列最長 10萬個字，沒測資不確定是否可行，應該最多 30x25x10^5
// 因為英文字母最多26個，將字串的min(前25字,字串長-1)串接在字串後 即可達到環狀的效果
// 擴增字串從第1字開始，出現的字母記號並記數，直到重複，下一段由被重複的下1字開始
// npsc2015-j1e NPSC2015國中組初賽 E.小希取名字
// 因為英文字母最多26個，將字串的min(前25字,字串長-1)串接在字串後 即可達到環狀的效果
// 擴增字串從第1字開始，出現的字母記號並記數，直到重複，下一段由被重複的下1字開始
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MaxN = 100000;
char s[MaxN+50];
int main( )
{
int t, i,j,k,a, n,m;
cin >> t;
for(i=0; i<t; ++i)
{
scanf("%s",s);
n = strlen(s);
// cout << n <<" : " << s ;
k = min( n-1 , 25 );
for(a=0,j=n; a<k; ++a, ++j) s[j]=s[a];
s[j]= '\0'; m=j;
// cout << " , " << m <<" : " << s << endl;
int ans=0, cnt=0;
int mk[99];
for(k=65;k<=90;++k) mk[k]=-1;
for(j=0; j<m; ++j)
{
if( mk[s[j]]>=0 ) //出現過
{
if(cnt>ans) ans=cnt;
cnt = 0;
j = mk[s[j]];
if(j>=n) break;
for(k=65;k<=90;++k) mk[k]=-1;
}
else
{
mk[s[j]] = j;
++cnt;
}
} // for j
if(cnt>ans) ans=cnt;
cout << ans << endl;
}
return 0;
}
/*
5
XDDORZQQ
IKKZZZSSH
ABCXYADFGXHJNDEGJK
ABCXYADFGXHJNDEGVK
OPWQHJNLVEGMKABCXYADFGXHJNCXYADFGXCXYADFGX
------------
5
4
11
13
18
*/