算法题：poj 2541 Binary Witch（KMP水过，逆序转换）

算法题：poj 2541 Binary Witch（KMP水过，逆序转换）2014-03-17 csdn博客 shuangde800链接：

http://poj.org/problem？id=2541

分析与总结：

做这题估算了下复杂度，觉得无论KMP再怎么快，这题暴力也肯定要超时的。

想了很久也没想出个好办法，于是决定暴力之，但是TLE了....于是就放了几天。之后看了下discuss ，这题的正解应该是状态压缩dp，不过目前我还不懂，跪了。

之后百度发现也可以用KMP水过，虽然是因为数据水才过的，不过这种思路很巧妙，值得借鉴！

直接暴力是枚举字符串的后面13个的字母，然后再用KMP匹配，这样的话，就绪要枚举多次，分别是后面的13，12，11....1个字母。但是通过观察可以发现，其实要求的是最长公共后缀！那么可以把原来的字符串逆序转换一下，就变成了求最长公共前缀！这样只需要求一次，用字符串的前面13个字母和原字符串进行匹配一次就够了！

分析与总结：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 1002000;const int START = 2000;char T[MAXN];intf[MAXN];int n,L;inline char getFail（char* p,int len）{int n=strlen（p）;f[0]=f[1]=0;int pos=-1, Max=-1;for（int i=1; i<n; ++i）{int j=f[i];while（j && p[i]！=p[j]）j=f[j];f[i+1] = p[i]==p[j]？1+j:0;if（f[i]==13）{return p[i-f[i]-1];}if（Max<f[i]）Max=f[i], pos=i-f[i]-1;}if（Max==-1）return "0";return p[pos];}int main（）{while（scanf（"%d%d%*c",&n,&L）！=EOF）{char *p;char *str = T+START;p=str;gets（str）;// 逆序转换int len=strlen（str）;for（int i=0,j=len-1; i<len/2; ++i,--j）{char t=str[i];str[i] = str[j];str[j] = t;}for（int i=0; i<L; ++i）{*（str-1）=getFail（str,len）;--str;++len;}--p;while（p>=str）{putchar（*p）;--p;}puts（""）;}return 0;}