现在的位置: 首页 > 综合 > 正文

3.1 字符串移位包含的问题——编程之美

2013年10月17日 ⁄ 综合 ⁄ 共 664字 ⁄ 字号 评论关闭

a. 问题:

       给定两个字符串s1和s2,要求判定s2是否能够被s1做循环移位(rotate)得到的字符串包含。例如,给定s1 = "AABCD",s2 = "CDAA",返回true;给定s1 = "ABCD",s2 = "ACBD",返回false。

b. 分析:
       在s1中从头至尾查找与s2中第一个元素相等的元素,找不到,则标志位mark为0,返回为false;若找到,则比较下一个元素,依次往下比较,当存在不相等的情况时,结束本次比较,I++,在s1中继续寻找与s2首元素相等的元素,重复以上比较,直到i增加到S1.size()结束。

c. 代码如下:
#include <iostream>
using namespace std;

int main()
{
	//string s1 = "AABCD",s2 = "CDAA";
	string s1 = "ABCD",s2 = "3ACBD";
	int i = 0,mark = 0;//注意:必须初始化mark为0.
	int length = s1.size();

	while (i < length)
	{
		if (s1[i] == s2[0])
		{
			for (int k = i,j = 0;j < s2.size();k++,j++)
			{
				if(s1[k%length] != s2[j])
				{
					mark = 0;//mark为0则说明不存在包含关系
					break;
				}
				mark = 1;   //循环进行到末尾,说明存在包含关系
			}
		}
		i++;
	}

	if (mark == 0)
	{
		cout << "false" << endl;
		return false;
	}
	else
	{
		cout << "true" << endl;
		return true;
	}
}
【上篇】
【下篇】

抱歉!评论已关闭.