POJ1035&&POJ3080&&POJ1936

字符串处理专题，很早就写好了然而忘记写blog了

1035

题意：给你一些单词作为字典。然后让你查找一些单词。对于每个单词，如果在字典中就输出它。否则输出所有它通过删除||增加||替换一个字符能得到的单词

由于数据范围很小，所以我们直接暴力跑一下即可

CODE

#include<string>

#include<iostream>

#include<map>

using namespace std;

const int N=10005;

map <string,bool> hash;

string s[N],t;

int n,m;

inline void swap(string &a,string &b)

{

	string temp=a; a=b; b=temp;

}

inline bool cmp(string a,string b)

{

	int len_a=a.size(),len_b=b.size();

	if (len_a<len_b) swap(a,b),len_a=a.size(),len_b=b.size();

	if (len_a-len_b>1) return 0;

	if (len_a^len_b)

	{

		for (register int i=0;i<len_a;++i)

		{

			string temp=a;

			temp.erase(i,1);

			if (temp==b) return 1;

		}

		return 0;

	} else

	{

		int tot=0;

		for (register int i=0;i<len_a;++i)

		{

			if (tot>1) return 0;

			if (a[i]^b[i]) ++tot;

		}

		return tot<=1;

	}

}

int main()

{

	register int i;

	std::ios::sync_with_stdio(false);

	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

	while (cin>>s[++n],s[n]!="#")

	hash[s[n]]=1; --n;

	while (cin>>t,t!="#")

	{

		if (hash[t]) cout<<t<<" is correct"<<endl; else

		{

			cout<<t<<":";

			for (i=1;i<=n;++i)

			if (cmp(s[i],t)) cout<<" "<<s[i];

			cout<<endl;

		}

	}

	return 0;

}

3080

题意是给你一些字符串，让你找它们的最长公共字串

同样因为范围很小，所以只需要枚举+find即可

CODE

#include<iostream>

#include<string>

using namespace std;

string s[15],ans;

int n,m,len,tot;

int main()

{

	register int i,j,k;

	ios::sync_with_stdio(false);

	cin>>n;

	while(n--)

	{

		cin>>m; tot=0; ans="";

		for (i=1;i<=m;++i)

		cin>>s[i]; len=s[1].size();

		for (i=0;i<len;++i)

		for (j=len-1;j>=i+tot-1;--j)

		{

			string temp(s[1],i,j-i+1);

			bool flag=1;

			for (k=2;k<=m;++k)

			if (s[k].find(temp)==string::npos) { flag=0; break; }

			if (flag)

			{

				if (temp.size()>tot) tot=temp.size(),ans=temp; else

				if (temp.size()==tot&&temp<=ans) ans=temp;

			}

		}

		if (ans.size()<3) cout<<"no significant commonalities"<<endl; else cout<<ans<<endl;

	}

	return 0;

}

1936

题意：对于两个字符串，判断s1是否为s2的一个子序列

注意这里是子序列，所以不能上find，手动模拟一个一个查找即可

CODE

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

char s1[100005],s2[100005];

int len1,len2,p;

int main()

{

	register int i;

	while (scanf("%s%s",&s1,&s2)!=EOF)

	{

		len1=strlen(s1); len2=strlen(s2); p=0;

		bool flag=1;

		for (i=0;i<len1;++i)

		{

			while (s2[p]!=s1[i]&&p<len2) ++p; ++p;

			if (p>len2) { flag=0; break; }

		}

		puts(flag?"Yes":"No");

	}

	return 0;

}

巴特西

POJ1035&&POJ3080&&POJ1936

最新文章

热门文章