2013
12-29

# 剪花布条

abcde a3
aaaaaa  aa
#

0
3

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#define X first
#define Y second
#define sqr(x) (x)*(x)
using namespace std;
const double PI = acos(-1.0);
map<int, int>::iterator it;
typedef long long LL ;
template<typename T> void checkmin(T &x, T y) {x = min(x, y);}
template<typename T> void checkmax(T &x, T y) {x = max(x, y);}

const int N = 1005;
int p[N];
int KMP(char *a, int n, char *b, int m) {
p[0] = -1;
int i, j = -1;
for(i = 1; i <= m; i++) {
while((j > -1) && (b[j+1] != b[i]))
j = p[j];
if(b[j+1] == b[i]) j++;
p[i] = j;
}
int cnt=0;
//for(i=0;i<m;i++) printf("%d   ",p[i]); printf("\n");
j = -1;
for(i = 0; i < n; i++) {
while((j > -1) && (b[j+1] != a[i])) j = p[j];
if(b[j+1] == a[i]) {
j++;
}
if(j == m - 1) {
++cnt;
j=0;
//printf("i=%d\n",i);
//return i-m+1;
j = p[j];
}
}
return cnt;
}
char s[N],t[N];
int main() {
while(~scanf("%s",s),s[0]!='#')
{
scanf("%s",t);
int n = strlen(s), m = strlen(t);
int res = KMP(s,n,t,m);
printf("%d\n",res);
}
}

1. 有一点问题。。后面动态规划的程序中
int dp[n+1][W+1];
会报错 提示表达式必须含有常量值。该怎么修改呢。。

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环