【题目】
给定两个字符串s1和s2,要求判断s2是否能够被通过s1做循环移位(rotate)得到的字符串包含。例如,S1=AABCD和s2=CDAA,返回true;给定s1=ABCD和s2=ACBD,返回false。
【分析】
【思路一】
从题目中可以看出,我们可以使用最直接的方法对S1进行循环移动,再进行字符串包含的判断,从而遍历其所有的可能性。
字符串循环移动,时间复杂度为O(n),字符串包含判断,采用普通的方法,时间复杂度为O(n*m),总体复杂度为O(n*n*m)。
字符串包含判断,若采用KMP算法,时间复杂度为O(n),这样总体的复杂度为O(n*n)。若字符串的长度n较大,显然效率比较低。其中n为S1的长度,m为S2的长度。
【思路二】
我们也可以对循环移位之后的结果进行分析。
以S1 = ABCD为例,先分析对S1进行循环移位之后的结果,如下所示:
ABCD--->BCDA---->CDAB---->DABC---->ABCD……
假设我们把前面的移走的数据进行保留,会发现有如下的规律:
ABCD--->ABCDA---->ABCDAB---->ABCDABC---->ABCDABCD……
因此,可以看出对S1做循环移位所得到的字符串都将是字符串S1S1的子字符串。如果S2可以由S1循环移位得到,那么S2一定在S1S1上,这样时间复杂度就降低了。
【代码一】
/*********************************
* 日期:2014-5-15
* 作者:SJF0115
* 题号: 字符串移位包含问题
* 来源:编程之美
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
bool IsRotate(char* str1,char* str2){
int i,j;
if(str1 == NULL || str2 == NULL){
return false;
}
int len = strlen(str1);
//循环移位
for(i = 0;i < len;i++){
char temp = str1[0];
//移动一位
for(j = 1;j < len;j++){
str1[j-1] = str1[j];
}
str1[len-1] = temp;
//判断str1中是否包含str2
if(strstr(str1,str2) != 0){
return true;
}
}
return false;
}
int main(){
char str1[6] = "AABCD";
char str2[5] = "CDAA";
bool result = IsRotate(str1,str2);
cout<<result<<endl;
return 0;
}
【代码二】
/*********************************
* 日期:2014-5-15
* 作者:SJF0115
* 题号: 字符串移位包含问题
* 来源:编程之美
**********************************/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
bool IsRotate(char* str1,char* str2){
int i,j;
if(str1 == NULL || str2 == NULL){
return false;
}
int len1 = strlen(str1);
char* str3 = new char(len1*2+1);
strcpy(str3,str1);
strcat(str3,str1);
//str3 = str1+str1
if(strstr(str3,str2) != 0){
return true;
}
return false;
}
int main(){
char str1[6] = "AABCD";
char str2[5] = "CDAA";
bool result = IsRotate(str1,str2);
cout<<result<<endl;
return 0;
}
分享到:
相关推荐
1.7 编程基础之字符串 python版.rar
本篇文章是对字符串移位包含的问题的解决方法进行了详细的分析介绍,需要的朋友参考下
第一节、一道俩个字符串是否包含的问题 1.1、O(n*m)的轮询方法 1.2、O(mlogm)+O(nlogn)+O(m+n)的排序方法 1.3、O(n+m)的计数排序方法 第二节 2.1、O(n+m)的hashtable的方法 2.2、O(n+m)的数组存储方法 ...
不使用库函数strcpy(),编程实现将字符串b复制到字符串a中,不使用库函数strcpy(),编程实现将字符串b复制到字符串a中,不使用库函数strcpy(),编程实现将字符串b复制到字符串a中,不使用库函数strcpy(),编程实现将...
精彩编程与编程技巧-字符串中包含双引号 ...
1.7编程基础之字符串(30题)--题目 有链接.pdf
indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。如果要检索的字符串值没有出现,则该方法返回 -1。 方法二:match() var str = "123" var reg = RegExp(/3/); if(str.match(reg)){ //包含; } ...
对C语言中字符串循环移位的问题进行详解,并给出两种方法求解。
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的字符操作包括 (1)删除一个字符; (2)插入一个字符; ...对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。
第一、找出字符或者字符串的类型,是数字、字母还是其他特定字符,是可打印字符,还是不可打印字符(一些控制字符)。 第二、找出组成字符串的字符个数和字符串的存储结构(比如数组)。 第三、对串的常规操作:求子串、...
python编程题:字符串的(所有可能的)排列组合全文共3页,当前为第1页。python编程题:字符串的(所有可能的)排列组合全文共3页,当前为第1页。python编程题:字符串的(所有可能的)排列组合 python编程题:字符...
c语言基础 c语言基础_c语言编程基础之字符串操作_查找常用字符串
精彩编程与编程技巧-字符串中文的问题 ...
本文实例讲述了Java编程实现中英混合字符串数组按首字母排序的方法。分享给大家供大家参考,具体如下: 在Java中对于字符串数组的排序,我们可以使用Arrays.sort(String[])方法很便捷的进行排序。例如: String[]...
编写程序:从键盘上输入一个包含10个字符的字符串,把该字符串与程序中给定的字符串("bacdbcabca") //依次比较,统计两个字符串对应字符相等的数目。然后输出从键盘上输入的字符串, //并把两个字符串中对应字符不...
C#字符串删除指定字符串|C#字符串删除子字符串
我们在编程的时候经常会碰到字符串分割的问题,这里总结下,也方便我们以后查询使用。 一、用strtok函数进行字符串分割 原型: char *strtok(char *str, const char *delim); 功能:分解字符串为一组字符串。 参数...
字符串比较问题 Description ?问题描述: 对于长度相同的2 个字符串A和B,其距离定义为相应位置字符距离之和。2 个非空格 字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0;空格与其它字符的距 离...
输入一个字符串参数,返回该字符串的反序字符串