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

链接：

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];
int  f[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;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索字符串
， int
， 这题怎么做啊
， include
， acm 算法 暴力
， kmp
， cc2541 ti
， cc2540 cc2541
， 字母大小写转换 算法
， 算法题
， 字母
， 逆序
暴力算法
cc2541、cc2541被动扫描、cc2541中文数据手册、cc2540 cc2541 区别、cc2541蓝牙模块，以便于您获取更多的相关知识。