#include <iostream> #include <cstring> #include <cstdio> #include <string> using namespace std; int lps[1000005]; void prefixArray(string s) { memset(lps,0,sizeof(lps)); int len=0;//length of prev longest prefix int i=1; lps[0]=0; int length = s.size(); while(i<length) { if(s[i]==s[len]) { len+=1; lps[i]=len; i+=1; } else { if(len!=0) { len = lps[len-1]; } else { lps[i]=0; i+=1; } } } }
Category: KMP Algorithm
1282
Theory: The idea for solving the problem is: for any fibonacci word F(n) = F(n-1)+F(n-2) = F(n-2)+F(n-3)+F(n-2), so word F(n-2) is both suffix and prefix of word F(n). After observing a little more we can find that F(n-2) will always be the prefix for all the rest of the fibonacci word.Now find the minimum F(n-3)
11475
#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <cstdlib> #define INF 1000000 #define ll long long using namespace std; int main() { char s[100005]; string str; int len,i,j,idx; int *failureFunc; while(scanf("%s",s)!=EOF) { len=strlen(s); str=""; for(int y=len-1;y>=0;y–) str.append(1u,s[y]); failureFunc=(int *)malloc(sizeof(int)*len); failureFunc[0]=0; i=0; j=1; while(j<len) { if(str[i]==str[j]) { i+=1; failureFunc[j]=i; j+=1; }
10679
KMP algo solution* */ /* #include<stdio.h> #include<string.h> #include<stdlib.h> #include <iostream> using namespace std; void computeLPSArray(char *pat, int M, int *lps); bool KMPSearch(char *pat, char *txt) { int M = strlen(pat); int N = strlen(txt); // create lps[] that will hold the longest prefix suffix values for pattern int *lps = (int *)malloc(sizeof(int)*M); int j =