蓝桥杯2014年第五届真题-重复模式

题目

题目链接

题解

暴力+STL。

只要是字符串暴力，和STL中的string及其函数就脱不了干系。

二分长度，check函数就获取全部此长度下的子串，若存在某个其他的子串与这个子串相等，那么就返回true。

通过find函数判断是否找到与枚举的子串一致的子串时，要注意使用s.find(str, i)格式，表示的是从索引为i处开始查找字符串s中是否存在子串str，这样可以避免因为找到的子串就是枚举的子串而返回true的情况。

不二分我不知道能不能过，没试。反正用二分显示0ms。 二分的话，就用y总的二分模板就行：（本题要用模板2）

// 模板1：
int bsearch_1(int l, int r)
{
    while (l > 1;  // 向下取整
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
 
// 模板1的的思考思路是:把mid分给了右半边,从右边向左找 每次比较的是a[mid]与target的= 关系
// 左侧都是不满足的，右侧都是满足的

// 模板2
int bsearch_2(int l, int r)
{
    while (l > 1;  // 向上取整
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
 
// 模板2的的思考思路是:把mid分给了左半边,从左边向右找 每次比较的是a[mid]与target的= 关系
// 左侧都是满足的，右侧都是不满足的

代码

#include
using namespace std;

string s;
int n;


bool check(int len) {  
	for(int i = 0;i+len-1 >s;
	n = s.size();
	int l = 0, r = n;
	while(l >1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	} 
	
	cout