本文主要是介绍poj 2541 Binary Witch (KMP+逆序转换+字符数组前端插入)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、http://poj.org/problem?id=2541
2、题目大意：
给定一个字符串，有N个字符，这N个字符只有0和1组成，表示N天的天气，0代表下雨，1代表晴天，现在要根据这N天的天气预测后边的连续L天的天气，规则是如果能找到一个下标K满足ak = aN-t+1, ak+1 = aN-t+2, ..., ak+t-1 = aN，那么ak+t就是第N+1天的天气，t从13开始取，一次取到1，如果不能满足，那么第N+1天的天气是0，如果能满足，并且有多个可以满足的，那么输出最往右的那个天气
此题可以将给定的前N天的天气字符串，逆转，那么此题就转换成求与前缀相同的字符串的最长长度的后一个字符，
用KMP失配函数
3、题目：
F - KMP 逆序转换
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Appoint description:
Description
Once upon a time in the silent depths of digital forests there lived a Binary Witch. She was able to forecast weather, telling for any day in the future whether it will be rainy or sunny.
Her magic was based on the following ancient rule: let a1, a2, ..., aN be the sequence of binary digits, where ai = 0 indicates that i-th day was rainy, and ai = 1 -- that it was sunny. To predict the weather in day N+1, consider the t-postfix a N-t+1, a N-t+2, ..., aN consisting of the last t elements. If that postfix is encountered somewhere before the position N-t+1, i.e. if there is such k <= N-t, that ak = a N-t+1, a k+1 = a N-t+2, ..., a k+t-1 = aN then the predicted value will be a k+t.
If there is more than one occurrence of t-postfix, then the rightmost one (with maximal k) will be taken. So, to make a prediction, she tried t-postfixes, consequently for t = 13, 12, ..., 1, stopping after the first prediction. If neither postfix was found, she predicted rain ("0"). If prediction for more than one day is needed, it is assumed that all previous days are predicted correctly, so if first predicted value is b, then we make forecast for day N+2 based on N+1 values, where a N+1 = b.
Because the witch was burned long ago, your task is to write a program to perform her arcane job.
Her magic was based on the following ancient rule: let a1, a2, ..., aN be the sequence of binary digits, where ai = 0 indicates that i-th day was rainy, and ai = 1 -- that it was sunny. To predict the weather in day N+1, consider the t-postfix a N-t+1, a N-t+2, ..., aN consisting of the last t elements. If that postfix is encountered somewhere before the position N-t+1, i.e. if there is such k <= N-t, that ak = a N-t+1, a k+1 = a N-t+2, ..., a k+t-1 = aN then the predicted value will be a k+t.
If there is more than one occurrence of t-postfix, then the rightmost one (with maximal k) will be taken. So, to make a prediction, she tried t-postfixes, consequently for t = 13, 12, ..., 1, stopping after the first prediction. If neither postfix was found, she predicted rain ("0"). If prediction for more than one day is needed, it is assumed that all previous days are predicted correctly, so if first predicted value is b, then we make forecast for day N+2 based on N+1 values, where a N+1 = b.
Because the witch was burned long ago, your task is to write a program to perform her arcane job.
Input
First line of input file contains two integers N (1 <= N <= 1000000) and L (1 <= L <= 1000), separated by space. Second line contains a string of N characters "0" and "1".
Output
Output file must contain a single string of L characters, which are forecasts for days N+1, N+2, ..., N+L.
Sample Input
10 7 1101110010
Sample Output
0100100
#include<stdio.h>
#include<string.h>
#define N 1000005
#define L 1005
char T[N+2*L];
char b[N+2*L];
int f[N+2*L];
char getFail(char *p, int *f)
{int m=strlen(p);f[0]=f[1]=0;int MAX=-1,pos;for(int i=1; i<m; ++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];else if(f[i]>MAX){MAX=f[i];pos=i-f[i]-1;}}if(MAX==-1)return '0';elsereturn p[pos];
}
int main()
{int n,l;scanf("%d%d",&n,&l);char *str=T+L;char *p=str;scanf("%s",str);int len=strlen(str);int j=0;for(int i=len-1;i>=0;i--)b[j++]=str[i];strcpy(str,b);//printf("%s\n",str);for(int i=0;i<l;i++){*(str-1)=getFail(str,f);--str;}--p;while(p>=str){printf("%c",*p);--p;}printf("\n");return 0;
}
这篇关于poj 2541 Binary Witch (KMP+逆序转换+字符数组前端插入)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
