小明OJ——字符串移位包含问题

题目描述

对于一个字符串来说，定义一次循环移位操作为：将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串 s1 和 s2，要求判定第二个字符串是否为第一个字符串通过若干次循环移位后的新字符串的子串。例如 CDAA 是由 AABCD 两次移位后产生的新串 BCDAA 的子串，而 ABCD 与 ACBD 则不能通过多次移位来得到其中一个字符串是新串的子串。

输入

一行，包含两个字符串 s1 和 s2，中间由单个空格隔开。字符串只包含字母和数字，长度不超过 30。

输出

如果 s2 是 s1 通过若干次循环移位产生的新串的子串，则输出循环移位的操作次数，否则输出 −1。

样例输入输出

样例输入 #1

AABCD CDAA

样例输出 #1

2

样例输入 #2

AAAAA ABC

样例输出 #2

-1

题解：

这是一道运用了几乎所有字符串知识的综合题，仔细分解后可以用两种方法得出每个步骤：

方法一：

第一种方法就是运用两个例题的标程核心段东拼西凑写出的，以下为程序的步骤：

1.判断s1的长度是否大于s2的长度，若是则继续，若否则输出-1并结束程序。（输入和记录长度的步骤省掉了）

2.判断s2是不是一开始就为s1的子串，若否则继续，若是则输出0并结束程序。

3.进行字符串位移。

4.判断s2是不是为s1的子串，若否则继续，若是则输出次数并结束程序。

5.返回第3个步骤，循环s1的长度次。

6.能留到这儿的都是真的不包含的，所以输出-1并结束程序。

虽然思路很棒，但是由于本人基本功不是特别好，所以只写出了49分的程序。

程序：

#include<bits/stdc++.h>
using namespace std;
string s,t;
int main(){
    cin>>s>>t;
    int ls=s.size(),lt=t.size(),i=0;
    if(ls<lt){
    	cout<<-1;
    	return 0;
	}
	for(int j=0,k,l;j+lt<=ls;j++){
    	for(k=j,l=0;k<lt;l++,k++)
    		if(s[k]!=t[l])
   				break;
    	if(l==lt){
    		cout<<i;
   			return 0;
		}
	}
    for(i=0;i<ls;i++){
    	char c=s[0];
		for(int j=1;j<ls;j++)
			s[j-1]=s[j];
		s[ls-1]=c;
    	for(int j=0,k,l;j+lt<=ls;j++){
    		for(k=j,l=0;k<lt;l++,k++)
    			if(s[k]!=t[l])
    				break;
    		if(l==lt){
    			cout<<i;
    			return 0;
			}
		}
	}
    cout<<-1;
    return 0;
}

方法二：

这次是运用到了环形子串的知识再加亿点点判断还有另类的输出写出了AC的程序，以下为程序的步骤：

1.定义一个判断子串的函数。

2.判断s1的长度是否大于s2的长度，若是则继续，若否则输出-1并结束程序。（输入和记录长度的步骤省掉了）

3.循环判断s2是不是一开始就为s1的子串，若否则继续，若是则输出0并结束程序，这里可以直接调用程序。

4.复制s1至它的后方。

5.循环判断s2第一此出现的下标，若没则继续，若找到了则输出下标加s2的长度减去s1的长度并结束程序，这里也可以直接调用程序。

6.能留到这儿的都是真的不包含的，所以输出-1并结束程序。

AC程序：

#include<bits/stdc++.h>
using namespace std;
char s[40],t[40];
int ls,lt;
bool f(int idx,int len){
	for(int i=idx,j=0;j<len;i++,j++)
		if(s[i]!=t[j])
			return false;
	return true;
}
int main(){
	cin>>s>>t;
	ls=strlen(s);
	lt=strlen(t);
	if(ls<lt){
		cout<<-1;
		return 0;
	}
	for(int i=0;i+lt<=ls;i++)
		if(f(i,lt)){
			cout<<0;
			return 0;
		}
	for(int i=0,j=ls;i<ls;i++,j++)
		s[j]=s[i];
	for(int i=0;i<=ls;i++)
		if(f(i,lt)){
			cout<<i+lt-ls;
			return 0;
		}
	cout<<-1;
	return 0;
}

呼，终于AC了