关于codeforces的Many Equal Substrings的题解

题目描述
分析
n是输入字符串的长度，k是要实现最后输出的字符串中包含原字符串的组数。由于原字符串以第一个字符开始（0）的子串和原字符串中从某个位置开始（1~n-1）到原字符串结尾有相同的部分，所以我们要找到这个最大的子串来保证在完成k组原字符串的总输出字符个数最少。
方法
（1）将整个字符串扫一遍，记录下从下表1开始于下表0相同字符的位置，并将其存入数组当中。
（2）设置一个i指向原字符串中下标为0的位置，设置一个j指向第一个出现和下表为0相同字符的位置。
（3）利用i和j当前指向的元素进行对比。如果当前两个元素相等且当前元素的下两个元素也相等，则此时i和j都向后移动一个位置（但一定要保证i和j不越界）
（4）倘若（3）条件无法满足，则i调回0位置，j从第二个出现与0位置字符相等的地方开始比较当前字符
code：

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
int main(){
	int n,k;
	string s,ss;
	while(cin>>n>>k){
		cin>>s;
		int i=0,j,count=0;
		int mark[50]={0};
		int c=0;
		for(int m=1;m<s.length();m++){
			if(s[m]==s[0]){
				mark[c++]=m;
			}	
		}
		int maximun=c;
		if(c==0){
			j=1;
		}
		else{
			c=0;
			j=mark[c];
		}
		
		while(j<s.length()&&i<s.length()){
			if(s[i]==s[j]){
				if(s[i+1]==s[j+1]&&i<s.length()-1&&j<s.length()-1){
					i++;
					count++;
					j++;
				}
				else if(s[i+1]!=s[j+1]&&(i<s.length()-1)&&(j<s.length()-1)){
					i=0;
					if(c<maximun){
						j=mark[c++];
					}
					else{
						count=0; 
						break;
					}
					count=0;
				}
				if(j==s.length()-1){
					count++; 
					break;
				}
			}
			else{
				j++;
				i=0;
				count=0;
			}
		}
		for(int p=count;p<s.length();p++){
			ss.push_back(s[p]);
		}
		cout<<s;
		for( i=1;i<k;i++){
			cout<<ss;
		}
		cout<<endl;
		ss.clear();
	}
	return 0;
}

关于codeforces的Many Equal Substrings的题解

相关推荐