题目链接
Red Rover
题意
给定一个字符串s，s由N、S、E、W组成。现引入一个M，可以用M来替代s中的子串，形成两个字符串s‘和子串，使得两个字符串的长度和小于原字符串的长度。 比如WNEENWEENEENE，用M来替代EEN，形成两个字符串WNMWMME和EEN。
分析
通过一个二重循环枚举所有子串(i,j),调用一个函数cnt来计算子串(i,j)在原串不重叠出现的次数。 cnt函数： 枚举起点，当起点相等时，比较后续的字符是否相等，然后进行计数并更新起点。
AC代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=
110;
string s;
int cnt(
int l,
int r)
{
int len=r-l+
1,ret=
0;
for(
int i=
0;i+len-
1<s.size();i++)
{
if(s[i]==s[l])
{
int j=
0;
for(j=
0;j<len;j++)
{
if(s[i+j]==s[l+j])
continue;
else break;
}
if(j==len)
{
ret++;
i+=len-
1;
}
}
}
return ret;
}
int main()
{
while(
cin>>s)
{
int ans=s.size();
int len=ans;
for(
int i=
0;i<s.size();i++)
for(
int j=i;j<s.size();j++)
{
int x=cnt(i,j);
ans=min(ans,len-x*(j-i+
1)+x+j-i+
1);
}
cout<<ans<<endl;
}
return 0;
}
