学步园

Description

给定一个字符串S[1..n]和一个整数T，现在需要在字符串S中找出长度不小于T的一个子串，使得其在原串中不重叠出现的次数最多，求这个次数。

Input

第一行：一个整数T(T > 1)
第二行：一个字符串S，且仅包含小写字母，字符串长度不超过10000

Output

一个整数。代表出现最多的次数
如果没有满足条件的解则输出0

Sample Input

2

ababab

Sample Output

3

#include <iostream><br /> using namespace std;<br /> int main()<br /> {<br /> int maxtime = 0;<br /> char s[10000];<br /> int t;<br /> int len;<br /> int times = 3;<br /> int i, j, k; //loop variables<br /> char **strTest;<br /> bool *scan;<br /> cin >> t ;<br /> cin >> s ;<br /> len = strlen(s); //串长<br /> //max: 25MB<br /> strTest = new char*[len - t + 1] ;<br /> for ( i = 0 ; i < len-t+1 ; i ++ )<br /> {<br /> strTest[i] = new char[t];<br /> }<br /> scan = new bool[len - t + 1] ;<br /> for ( i = 0 ; i < len-t+1 ; i ++ )<br /> {<br /> scan[i] = false;<br /> }<br /> //取串<br /> for ( i = 0 ; i < len-t+1 ; i ++ )<br /> {<br /> for ( j = i ; j < i + t ; j ++ )<br /> {<br /> strTest[i][j - i] = s[j] ;<br /> }<br /> }<br /> //遍历比较<br /> for ( i = 0 ; i < len - t + 1 ; i ++ )<br /> {<br /> if ( ! scan[i] )<br /> {<br /> times = 0 ;<br /> for ( j = i ; j < len - t + 1 ; j ++ )<br /> {<br /> //strcmp要比较'/0'结束，因此在程序中越界<br /> if ( ! strncmp(strTest[i], strTest[j], t))<br /> {<br /> times ++ ;<br /> scan[j] = true ;<br /> j = j + t - 1 ;<br /> }<br /> }<br /> }<br /> scan[i] = true ;<br /> if (maxtime < times )<br /> {<br /> maxtime = times ;<br /> }<br /> }<br /> cout << maxtime << endl ;<br /> return 0;<br /> }<br />