hdu 4300 Clairewd’s message(KMP)

题目链接：hdu 4300 Clairewd’s message

题目大意：题目意思比较难懂，给出两个字符串，第一个字符串为编码规则，比如说样例1，q位于第一个位置，表示说q的编码是a。然后给出另一个字符串s，要求添加尽量少得字符，使得f可以被分成两部分f1+f2， 然后f1编码后等于f2，然后注意给出的f串为编码串，并非原串。

解题思路：首先先将f串转换成原串s，然后求出jump数组，去和f匹配，对于匹配的最后一项值p（即为最长匹配后缀），n-p即是我们要求的f1的长度（但是这里要注意n-p 不能小于p，因为分成两部分后不能说有公共的部分存在，所以p = jump[p]）

#include <stdio.h>
#include <string.h>

const int N = 1e5+5;

int n, jump[N];
char t[30], v[30], s[N], f[N];

void getJump () {
	int p = 0;
	for (int i = 2; i <= n; i++) {
		while (p > 0 && s[p+1] != s[i])
			p = jump[p];

		if (s[p+1] == s[i])
			p++;
		jump[i] = p;
	}
}

int KMP () {
	int p = 0;
	for (int i = 1; i <= n; i++) {
		while (p > 0 && s[p+1] != f[i])
			p = jump[p];

		if (s[p+1] == f[i])
			p++;

		if (p == n)
			p = jump[p];
	}

	while (n - p < p)
		p = jump[p];
	return p;
}

void init () {
	scanf("%s%s", t, f+1);
	n = strlen (f+1);
	for (int i = 0; i < 26; i++)
		v[t[i]-‘a‘] = i + ‘a‘;

	for (int i = 1; i <= n; i++)
		s[i] = v[f[i]-‘a‘];

	s[n+1] = ‘\0‘;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init ();

		getJump ();
		int k = n - KMP ();
		for (int i = 1; i <= k; i++)
			printf("%c", f[i]);
		for (int i = 1; i <= k; i++)
			printf("%c", v[f[i]-‘a‘]);
		printf("\n");
	}
	return 0;
}

hdu 4300 Clairewd’s message(KMP),布布扣,bubuko.com

hdu 4300 Clairewd’s message(KMP)

原文：http://blog.csdn.net/keshuai19940722/article/details/21560417