HDU2594-两串的最长相同前后缀

前言

这算不算是第一次写算法相关的博客呢… xswl，还在学OI的时候教练多次我们建议写博客，我当时不感兴趣，现在都退役多久了在 学 复习数据结构和算法的时候又突然想起写博客了hhh….

题目

问题描述

给定两个字符串s1和s2，求最长的s1前缀ss使得ss为s2的最长后缀，输出该字符串和其长度。

输入形式

输入的每个测试用例由两行构成，第一行为s1，第二行为s2。假设所有输入的数据均为小写字母。

输出形式

每个测试用例的输出由单行组成，其中包含最长的字符串，该字符串是s1的前缀和s2的后缀，后面跟着该前缀的长度。如果最长的此类字符串是空字符串，则输出应为0。s1和s2的长度最多为50000。

样例输入

aaariemann
marjorieaaa

样例输出

aaa

样例说明

输入的第一行字符串s1=‘aaariemann’，第二行字符串s2=‘marjorieaaa’。s1的前缀和s2的后缀最长相等字符串为aaa，因此输出aaa 3，而不是a 1。测试数据存放在in.txt文件中。

思路

思路1：kmp

把s2拼接到s1后面，用kmp算法求出这个新串的最大公共前后缀
但是有个问题，求出的 kmp[l1+l2] 可能会大于原串的长度
所以我们还需要回退直到小于两串长度中更小的一个

while(aans>min(l1,l2))
	aans=kmp[aans];

为什么这样做是对？因为这个新串的前 kmp[aans] 和后 kmp[aans] 个字符是相同的，那么它的前后 kmp[ kmp[aans] ] 个字符也是相同的（公共前后缀的公共前后缀），如果这个公共前后缀的公共前后缀依然比原串长，我们就继续回退直到得到的公共前后缀是原串的一个子串
当然也可以在拼接两个串时在中间插一个分隔字符，检测到之后就不再继续匹配

思路2：扩展kmp

还没复习所以先空着

代码

#include <iostream>
using namespace std;
int main()
{
	freopen("in.txt","r",stdin);
	string s1,s2;
	cin>>s1>>s2;
	int l1=s1.length(),l2=s2.length();
	s1="0"+s1;
	s1.append(s2);
	int l=s1.length()-1;
	int kmp[1000002]={0};
	int j=0;
	for(int i=2;i<=l;i++)
	{
		while(j&&s1[j+1]!=s1[i])j=kmp[j];
		if(s1[j+1]==s1[i])j++;
		kmp[i]=j;
	}
	int aans=kmp[l];
	while(aans>min(l1,l2))
		aans=kmp[aans];
	for(int i=1;i<=aans;i++)cout<<s1[i];
	cout<<" "<<aans;
	return 0;
}