题目来源：URAL 1684. Jack's Last Word

题意：输入a b 把b分成若干段 每一段都是a的前缀

思路：b为主串 然后用a匹配b 记录到b的i位置最大匹配的长度 然后切割 切割的时候要从后往前

假设a = abac b = abab 那么假设从前往后 首先覆盖了aba 然后b就不能覆盖了 从后往前就能够了 首先覆盖ab 下一次还是ab

由于已经记录了到i位置的最大匹配长度 依据长度从末尾倒退 每次倒退的时候仅仅要是最大的匹配的长度

由于假设在某一次的递推 记录的最大匹配的前缀是x 那么这次应该倒退到i-x

假设不倒退x 倒退小于x的字符y 而且x是能够倒退 剩下的是y-x必然能够倒退 那么一次解决即可了

#include <cstdio>

#include <cstring>

const int maxn = 100010;

char a[maxn], b[maxn];

int f[maxn];

int dp[maxn];

char c[maxn*2];

void get_fail(char* s)

{

	f[0] = f[1] = 0;

	int n = strlen(s);

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

	{

		int j = f[i];

		while(j && s[i] != s[j])

			j = f[j];

		if(s[i] == s[j])

			f[i+1] = j+1;

		else

			f[i+1] = 0;

	}

}

int main()

{

	while(scanf("%s %s", a, b) != EOF)

	{

		get_fail(a);

		int n = strlen(b), m = strlen(a);

		int j = 0;

		for(int i = 0; i < n; i++)

		{

			while(j && b[i] != a[j])

				j = f[j];

			if(a[j] == b[i])

				j++;

			dp[i] = j;

			if(j == m)

				j = f[j];			

		}

		c[n*2] = 0;

		int len = n*2, i;

		for(i = n-1; i >= 0; )

		{

			int k = dp[i];

			if(k == 0)

				break;

			for(int j = i; j > i-k; j--)

				c[--len] = a[j-i+k-1];

			c[--len] = ' ';

			i = i-k;

		}

		if(i != -1)

			puts("Yes");

		else

		{

			puts("No");

			puts(c+len+1);

		}

	}

	return 0;

}