HDU 1867 KMP maximum tail overlap

Recommended for you: Get network issues from WhatsUp Gold. Not end users.


Given 2 strings, A-B or B-A

The tail part of a same output only

For minimum string length (length of the same lexicographically least)

using namespace std;

#define N 200050

int f1[N], f2[N];
char s1[N], s2[N];

void getFail(int *f, char *s){
	int i, j, len = strlen(s);
	j = f[0] = -1;
	i = 0;
	while(i <len)
		while(j!=-1 && s[i] != s[j])j = f[j];
		i++, j++;
		if(s[i] != s[j])f[i] = j;
		else f[i] = f[j];
int KMP(int *f, char *S1, char *S2){
	int pos = 0, len = strlen(S1), j = 0, i = 0;
	while(i <= len)
		while(j!=-1 && S1[i] != S2[j]) j = f[j];
		i++, j++;
		if(i == len)pos = max(pos, j);
	return pos;
void go(char *S1, char *S2, int pos){
	int i = strlen(S1);
		S1[i++] = S2[pos++];
	S1[i] = '\0';
char tmp1[N], tmp2[N], as1[N], as2[N];
int main(){
	while(~scanf("%s %s", s1, s2)){
		getFail(f1, s1);
		getFail(f2, s2);
		int ans1 = KMP(f2, s1, s2), ans2 = KMP(f1, s2, s1);

			go(s1, s2, ans1);
		else if(ans1<ans2)
			go(s2, s1, ans2);
			memcpy(tmp1, s1, sizeof(s1));
			memcpy(tmp2, s2, sizeof(s1));
			go(tmp1, tmp2, ans1);
			memcpy(as1, tmp1, sizeof(as1));

			memcpy(tmp1, s1, sizeof(s1));
			memcpy(tmp2, s2, sizeof(s1));
			go(tmp2, tmp1, ans1);
			memcpy(as2, tmp2, sizeof(as1));

			if(strcmp(as1, as2) <0) 
	return 0;

asdf sdfg

asdf ghjk

aa aa

asdf sd

asdf df

aabbcc ccbbaa

aabbcdc fdssbbaa

sadsffxcvrg asdfrxccverasd

asdfrxccverasd sadsffxcvrg

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download

Posted by Tyrone at December 17, 2013 - 9:57 PM