hdu 4300KMP

这题纯属蹭过，按理说应该是扩展KMP的方法。我是直接用的KMP的next数组，特殊情况加以判断就过了。

/*
 * hdu4300/win.cpp
 * Created on: 2012-8-1
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAX_LEN = 100010;
char swit[128];
char pattern[MAX_LEN];
int next[MAX_LEN], parlen;
char getPlain(char c) {
    for(int i = 'a'; i <= 'z'; i++) {
        if(swit[i] == c) {
            return (char)i;
        }
    }
    return 0;
}
int work() {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < parlen) {
        if (j < 0 || swit[(int)pattern[i]] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    if(next[parlen - 1] == 0) {
        if(pattern[0] != swit[(int)pattern[parlen - 1]]) {
            return -1;
        }
    }
    if(next[parlen - 1] < (parlen / 2)) {
        return next[parlen - 1];
    }else {
        int xhj = parlen - next[parlen - 1] - 1;
        int xhs = parlen / xhj;
        if(xhs % 2 == 0) {
            return parlen / 2 - 1;
        }else {
            return (xhs / 2) * xhj - 1;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; t++) {
        char tempstr[200];
        scanf("%s%s", tempstr, pattern);
        parlen = strlen(tempstr);
        for(int i = 'a'; i <= 'z'; i++) {
            swit[i] = tempstr[i - 'a'];
        }
        parlen = strlen(pattern);
        int s = work() + 1;
//        printf("%d\n", s - 1);
        int e = parlen - s;
        printf("%s", pattern);
        for(; s < e; s++) {
            putchar(getPlain(pattern[s]));
        }
        putchar('\n');
    }
    return 0;
}