字符串包含--数组存储O（m+n）

#include<iostream>
#include<string>
using namespace std;


int main()
{
	char long_ch[]="TADBSROC";
	char short_ch[]="CADS";
	int i;
	bool store[58];
	memset(store,false,58);
	//前两个是遍历两个字符串，后面一个是遍历数组


	for(i=0;i<sizeof(short_ch)-1;i++)
		store[short_ch[i]-65]=true;
	for(i=0;i<sizeof(long_ch)-1;i++)
	{
		if(store[long_ch[i]-65]!=false)
			store[long_ch[i]-65]=false;
	}
	for(i=0;i<58;i++)
	{
		if(store[i]!=false)
		{
			cout<<"short_ch is not in long_ch"<<endl;
			break;
		}
		if(i==57)
			cout<<"short_ch is in long_ch"<<endl;


	}
	return 0;
}

同时还可以达到O(n)--O(m+n)之间，利用素数方法。定义最小的26个素数分别与字符A到Z对应，遍历长字符串，求得每个字符对应素数的乘积，遍历段字符串，判断乘积能否

被段字符串的字符对应的素数整除。若第一个数就不被整除，此时退出程序，时间复杂度最好为O（n）

#include<iostream>
#include<string>
#include "BigInt.h"
using namespace std;

//素数数组
int primeNumber[26] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
int main()
{
	string strOne = "RACBDOR";
	string strTwo = "DCRA";
	CBigInt product = 1;//大整数除法的代码
	//遍历长字符串，得到每个字符对应素数的乘积
	for(int i = 0;i<strOne.length();i++)
	{
		int index = strOne[i]-‘A‘;
		product = product * primeNumber[index];
	}
	//遍历短字符串
	for(int j = 0;j<strTwo.length();j++)
	{
		int index = strTwo[j]-‘A‘;

		if(product % primeNumber[index]!=0)
			break;
	}

	if(strTwo.length() == j)
		cout<<"true"<<endl;
	else
		cout<<"false"<<endl;
	return 0;
}

字符串包含--数组存储O（m+n）,布布扣,bubuko.com

字符串包含--数组存储O（m+n）

原文：http://blog.csdn.net/woailvmengmeng/article/details/23270771