Codeforces Round #106 (Div. 2) 149/E E. Martian Strings

/*
　　http://codeforces.com/problemset/problem/149/E
　　KMP结合动态规划的思想，正向匹配一边，l[]数组保存的是对于匹配串的每一个位置在模式串能匹配的最左边，也就是首次匹配的位置
　　逆序再匹配一次，逆向信息保存r[]数组。
　　再枚举l[i]+r[len-i]
*/
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int maxn = 1005;
const int inf = maxn*maxn+1;
int next[maxn];
char word[maxn];
char test[maxn*maxn];
char test_reverse[maxn*maxn];
int l[maxn],r[maxn];
void getnext(char str[]){
int i = 0,j = -1;
int len = (int)strlen(str);
next[0] = -1;
while(i < len){
if(j == -1 || str[i] == str[j]){
++i,++j;
if(str[i] == str[j])
next[i] = next[j];
else
next[i] = j;
}
else
j
= next[j];
}
}
void kmp(char str[],char pat[],int dp[]){
int i = 0,j = 0;
getnext(pat);
int len_str = (int)strlen(str);
int len_pat = (int)strlen(pat);
while(i < len_str&&j < len_pat){
if(j == -1 || str[i] == pat[j]){
i++;
j++;
dp[j] = min(dp[j],i);
}
else
j = next[j];
if(j == len_pat)
j = next[j];
}
}
void init(int len){
l[0] = 0,r[0] = 0;
for(int i = 1;i <= len;i++){
l[i] = inf;
r[i] = inf;
}
}
int main(){
while(~scanf("%s",test)){
int len = (int)strlen(test);
for(int i=0;i<len;i++)
test_reverse[i]=test[len-1-i];
int m;
scanf("%d",&m);
int ans = 0;
while(m--){
scanf("%s",word);
int len_word = (int)strlen(word);
if(len_word==1) continue;
init(len_word);
kmp(test,word,l);
reverse(word, word+strlen(word));
kmp(test_reverse, word, r);
//for(int i = 0;i < strlen(word);i++)
//
printf("%d %dn",l[i],r[i]);
for(int i = 1;i <= len_word;i++){
if(l[i] + r[len_word - i] <= len){
ans++;
break;
}
}
}
printf("%dn",ans);
}
return 0;
}