博客

最长公共字符串后缀

题目描述：

输入及输出样例：

输入:

3

baba

aba

cba

2

aa

cc

2

aa

a

0

输出:

ba

a

思路：

将每个字符串反转，原问题就成了：

最长公共字符串前缀


找到长度最小的字符串，从前往后截取长度1~minn.size()的字符串，将这个匹配串与每个字符串去比较

找到最后一个合法的匹配串，

再反转回去

，即为最大的公共后缀字符串。

CODE：

#include<iostream>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f
#define N 210

using namespace std;
ll n;
string s[N],minn;
int main()
{
	ios::sync_with_stdio(false);
	while(cin >> n,n)
	{
		ll t = INF;
		string ans = "";
		minn = "";
		for(int i = 1;i <= n;++i)
		{
			cin >> s[i];
			reverse(s[i].begin(),s[i].end());
			if(s[i].size() < t)//输入时就可以找到最小长度的串了。
			{
				t = s[i].size();
				minn = s[i];
			}
		}
		for(int i = 0;i < minn.size();++i)
		{
			string k = minn.substr(0,i + 1);//截取长度为i的字符串
			bool b = true;
			for(int j = 1;j <= n;++j)
			{
				if(k != s[j].substr(0,i + 1))//有一个不匹配就不是前缀
				{
					b = false;
					break;
				}
			}
			if(b) ans = k;//长度是在单调递增的，最后一个合法的一定是最长的
		}
		reverse(ans.begin(),ans.end());
		cout << ans << endl;
	}
	return 0;
}

可以看到，跑的还是蛮快的。

综上所述：

最长公共字符串前缀应该是这样的：

#include<iostream>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f
#define N 210

using namespace std;
ll n;
string s[N],minn;
int main()
{
	ios::sync_with_stdio(false);
	while(cin >> n,n)
	{
		ll t = INF;
		string ans = "";
		minn = "";
		for(int i = 1;i <= n;++i)
		{
			cin >> s[i];
			if(s[i].size() < t)
			{
				t = s[i].size();
				minn = s[i];
			}
		}
		for(int i = 0;i < minn.size();++i)
		{
			string k = minn.substr(0,i + 1);
			bool b = true;
			for(int j = 1;j <= n;++j)
			{
				if(k != s[j].substr(0,i + 1))
				{
					b = false;
					break;
				}
			}
			if(b) ans = k;
		}
		cout << ans << endl;
	}
	return 0;
}

感谢您的阅读，希望这篇题解能帮到您。