洛谷传送
牛客网题一
牛客网题二
没错牛客网有两个题，牛客网题一和洛谷是一样的题，牛客网题二是题一的变形

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
链接：https://ac.nowcoder.com/acm/contest/4860/G
来源：牛客网

输入描述:

  • Line 1: A single encrypted string of length at most 100.

输出描述:

  • Line 1: The number of ways FJ could have produced this string with one or more successive operations applied to some initial string of
    length at least 2, written out modulo 2014. If there are no such
    ways, output zero.

题一：

示例1
输入

ABABA

输出

8

题意：
一个长度至少为2仅包含字符A~Z的字符串。为了加密他的消息，FJ对这条消息进行了一系列“操作”。一次对字符串S的“操作”是指去掉S开头的若干个字母（但不是全部）或末尾的若干个字母（但不是全部），然后将原来的S拼接到开头或末尾。
给你操作后的字符串，问你操作前有几种情况？
我们看看样例：
ABABA
输出是8，哪8种呢？如下：

Start with ABA -> AB+ABA

Start with ABA -> ABA+BA

Start with AB -> AB+A -> AB+ABA

Start with AB -> AB+A -> ABA+BA

Start with BA -> A+BA -> AB+ABA

Start with BA -> A+BA -> ABA+BA

Start with ABAB -> ABAB+A

Start with BABA -> A+BABA

我们注意到什么样的可以作为操作前的候选串：至少可以通过拆分构造出原串的头和尾
我们可以这么想

分三种情况：
第一种：看头和尾
样例： A B A B A
首先首尾的两个字符相等（都是A），那也就是开头的可以被省掉，（因为省掉后BABA可以通过去除BAB后剩下A再加上原串BABA构成原本的ABABA，好好想想是不是），那同理结尾的A也可省略了，省略后就是ABAB。
省略后的BABA也进行这样的过程 ，看首尾分别是BA不相等，那指针都向中间移动，再看首（BA）尾（BA）是否相等，发现相等，那首可以省略吧，那尾也可以省略吧 ，这就是两种情况了。一直进行下去直到字符串的长度为2或者不满足条件
第二种：看开头
样例A B A B C
id 0 1 2 3 4
比较第一个开头（A（id=0））和第二个开头（B（id=1）），发现不一样范围同时扩大，第一个开头就是（A B（id=0,1）），第二个开头就是（A B（id=2,3）），发现相同那么第一个开头就可以省略了，就剩下ABC，但注意第二个开头不能省略，因为不能在中间断开，然后对ABC再进行操作
第三种：看结尾
样例C A B A B
其实第二种与第三种相同，看结尾就是倒着来，从开始B！=A，然后AB==AB，所以最后这个尾AB（id=34）就可以省略，剩下CAB _ _（下划线为省去的部分）,然后再进行操作
我们进行的顺序是第一种到第二再到第三，每次再进行操作时都要从第一种开始
在操作中我们需要截取字符串，就可以用substr（x，y）,从第id=x位开始截取，长度为y
但这题还有一个坑，方案数（用ans表示）开始必须为1，（就是他本身，表示不变换），但是应该输出变化后的方案，所以还要-1
对了每个出现的字符串都记录长度，下次遇见时直接返回值

#include<bits/stdc++.h>
const int mod=2014;
using namespace std;
map<string,int>a;

string find(string s,int x,int y)
{
   
//	cout<<6<<" "<<s.substr(x,y)<<endl;
	return  s.substr(x,y);
}
int count(string s)
{
   

	//	cout<<4<<" "<<s<<endl;
	if(a[s])return a[s];
	//	cout<<5<<" "<<s<<endl;
	int ans=1;
	int len=s.size();
	for(int i=1;i*2<len;i++)
	{
   
		if(find(s,0,i)==find(s,len-i,i))
		{
   
			ans=ans+count(find(s,i,len-i))+count(find(s,0,len-i));
		//		cout<<1<<" "<<s.substr(i,len-i)<<" "<<s.substr(0,len-i)<<endl;
		//	cout<<7<<" "<<ans<<endl;
		}
		if(find(s,0,i)==find(s,i,i))
		{
   
			ans=ans+count(find(s,i,len-i));
			//	cout<<2<<" "<<s.substr(i,len-i)<<endl;
			//		cout<<7<<" "<<ans<<endl;
		}
		if(find(s,len-i,i)==find(s,len-i-i,i))
		{
   
			ans+=count(find(s,0,len-i)); 
			//	cout<<3<<" "<<s.substr(0,len-i)<<endl;
				//	cout<<7<<" "<<ans<<endl;
		} 
		
	}
//	cout<<7<<" "<<ans<<endl;
	a[s]=ans%mod;
	return a[s];
}
int main()
{
   
	string c;
	cin>>c;
	int sum =0;
	sum =(count(c))%mod;
	cout<<sum-1;
	return 0;
	
}
//AAAAAAAAAAAAAAAAAAAA

代码中注释部分为我一开始用来调试的，因为一开始我将ans定义为全局变量而被疯狂卡o(╥﹏╥)o
**

题二：

**
链接：https://ac.nowcoder.com/acm/contest/4860/J
来源：牛客网

输入描述:

  • Line 1: A string of length at most 100.

输出描述:

  • Line 1: The number of different ways FJ could have produced this
    string by applying one or more successive operations to some
    source string of length at least 2. If there are no such ways,
    output zero.
    示例1
    输入 
ABABA

输出

6

说明

Here are the different ways FJ could have produced ABABA:

  1. Start with ABA -> AB+ABA
  2. Start with ABA -> ABA+BA
  3. Start with AB -> AB+A -> AB+ABA
  4. Start with AB -> AB+A -> ABA+BA
  5. Start with BA -> A+BA -> AB+ABA
  6. Start with BA -> A+BA -> ABA+BA
    题解：
    （我一开始以为两个一样直接提交代码，痛wa两次）
    题二也就是题一变形，不同处在于：
    一次对字符串S的“操作”是指去掉S开头的一个字母（而非原本的若干）或末尾的一个字母（而非若干），
    看样例：
    ABABA
    也就是ABAB和BABA这两种情况不存在，因为只能删去一个的话，删后字符串长为3，再加上原本的4=7超过了目标长度5
    我们设满足条件的字符串长度为x，目标字符串长度为len，那么删后为x-1，加在一起就是2x-1，要求2x-1<=n
    解得x<=(n+1)/2
    在代码中我们每次所截代码长度为len-i（详细看上个代码），所以len-i>(n+1)/2时就不满足题意，continue，不理这种情况，直接下一个。 
#include<bits/stdc++.h>
//const int mod=2014;
using namespace std;
map<string,long long int>a;

string find(string s,int x,int y)
{
   
//	cout<<6<<" "<<s.substr(x,y)<<endl;
	return  s.substr(x,y);
}
long long int count(string s)
{
   

	//	cout<<4<<" "<<s<<endl;
	if(a[s])return a[s];
	//	cout<<5<<" "<<s<<endl;
	long long int ans=1;
	long long int len=s.size();
	for(int i=1;i*2<len;i++)
	{
   
		if((len-i)>(len+1)/2)continue;//不同之处 if(find(s,0,i)==find(s,len-i,i))
		{
   
			ans=ans+count(find(s,i,len-i))+count(find(s,0,len-i));
	//			cout<<1<<" "<<s.substr(i,len-i)<<" "<<s.substr(0,len-i)<<endl;
	//		cout<<7<<" "<<ans<<endl;
		}
		if(find(s,0,i)==find(s,i,i))
		{
   
			ans=ans+count(find(s,i,len-i));
	//			cout<<2<<" "<<s.substr(i,len-i)<<endl;
	//				cout<<7<<" "<<ans<<endl;
		}
		if(find(s,len-i,i)==find(s,len-i-i,i))
		{
   
			ans+=count(find(s,0,len-i)); 
	//			cout<<3<<" "<<s.substr(0,len-i)<<endl;
	//				cout<<7<<" "<<ans<<endl;
		} 
		
	}
//	cout<<7<<" "<<ans<<endl;
	a[s]=ans;
	return a[s];
}
int main()
{
   
	string c;
	cin>>c;
	long long int sum =0;
	sum =count(c);
	cout<<sum-1;
	return 0;
	
}
//AAAAAAAAAAAAAAAAAAAA