NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組初賽
 NPSC2015國中組初賽 E.小希取名字

作者 主題: NPSC2015國中組初賽 E.小希取名字  (閱讀 961 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC2015國中組初賽 E.小希取名字
« 於: 十二月 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
*/
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2015國中組初賽
 NPSC2015國中組初賽 E.小希取名字