题目链接
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;//后面还有个i++}}}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;
}