Problem Description

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

 

Input

输入中含有一些数据，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。如果遇见#字符，则不再进行工作。

 

Output

输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就老老实实输出0，每个结果之间应换行。

 

Sample Input

 

Sample Output

 

#include <bits/stdc++.h>

using namespace std;

long long mod = 1e9 + 7;

long long base = 131LL;

const int maxn = 1e5 + 10;

char s[maxn], t[maxn];

int lens, lent;

long long b[maxn], sum[maxn], u[maxn];

long long Query(int L, int R) {

  long long res = sum[R];

  if(L - 1 >= 0) res = (res - sum[L - 1] + mod) % mod;

  return res;

}

int main() {

  u[0] = 1LL;

  for(int i = 1; i < maxn; i ++)

    u[i] = u[i - 1] * base % mod;

  while(~scanf("%s", s)) {

    lens = strlen(s);

    if(lens == 1 && s[0] == '#') {

      break;

    }

    scanf("%s", t);

    lent = strlen(t);

    long long hasht = 0;

    for(int i = 0; t[i]; i ++) {

      hasht = hasht * base % mod;

      hasht = (hasht + t[i]) % mod;

    }

    long long pow = 1LL;

    for(int i = lens - 1 ; i >= 0; i --) {

      b[i] = pow * s[i] % mod;

      pow = pow * base % mod;

    }

    sum[0] = b[0];

    for(int i = 1; i < lens; i ++) {

      sum[i] = (sum[i - 1] + b[i]) % mod;

    }

    int ans = 0;

    int p = 0;

    while(p < lens) {

      if(p + lent - 1 >= lens) break;

      int L = p, R = p + lent - 1;

      if(Query(L, R) == (hasht * u[lens - 1 - R] % mod)) {

        ans ++;

        p = p + lent;

      } else p ++;

    }

    printf("%d\n", ans);

  }

  return 0;

}