cf187 div2 D

 1 /*
 2   Problem:cf187 div2 D
 3   Type:string
 4   Time:2013.06.09 
 5   //思路，直接统计b字符串每个字符开始，经过一个a字符串的结果
 6     所谓结果，a的一个循环包含多少个当前字符后的字符
 7     保存完后对a统计即可 
 8     好吧，够绕口的，直接看代码比较清楚 
 9 */
10 #include <iostream>
11 #include <cstdio>
12 #include <cstdlib>
13 #include <cstring>
14 #include <cmath>
15 #include <algorithm>
16 #include <string>
17 #include <stack>
18 #include <set>
19 #include <queue>
20 #include <map>
21 #include <fstream>
22 #include <vector>
23 #include <list>
24 #define MaxPoint 20000
25 #define MaxLine 50
26 #define MaxNum 1999997
27 #define Inf 0xfffff
28 #define M0(a) memset(a, 0, sizeof(a))
29 using namespace std;
30 int n, m;
31 char a[200], b[200];
32 int next[200], cnt[200];
33 void solve(){
34       scanf("%s%s", &a, &b);  
35       int la = strlen(a), lb = strlen(b), cur;
36       
37       for (int i = 0; i < lb; ++i){
38           cur = i;
39           for (int j = 0; j < la; ++j) //从cur开始在一个周期的a的作用下能到达哪里，并统计当前答案，记住next数组 
40              if (a[j] == b[cur]){
41                 ++cur;
42                 if (cur == lb){
43                      ++cnt[i];
44                      cur = 0;
45                 }
46              }
47           next[i] = cur;
48       }
49       long long ans = cur = 0;
50       for (int i = 1; i <= n; ++i){ //直接计算每个a数组的答案 
51           ans += cnt[cur];
52           cur = next[cur];
53       }
54       printf("%I64d\n", ans / m);
55 }
56 
57 int main(){
58      freopen("a.in","r", stdin);
59      freopen("a.out","w", stdout);
60      scanf("%d%d", &n, &m);
61      solve();
62      fclose(stdin);   fclose(stdout);
63 }