2015
09-17

# Finding string

Richard is a smart data analyst in a famous company. One of his daily boring work is to find how many times does a pattern string occur in a very long string.
Luckily, Richard notices that there are many consecutive repeated substrings in this very long string, so he uses the following compression algorithm to make the string shorter:

a). Find a non-compressed consecutive repeated substring of the original string, e.g. “ab” in “cabababd”.
b). Replace the repeating part with the bracketed repetend, followed by the times the repetend appears in the original string. e.g. Write “cabababd” as “c[ab]3d”. Note she can also write it as “c[ab]1ababd” or “ca[ba]2bd” and so on, although these string are not compressed as well as the first one is.
c). Repeat a) and b) several times until the string is short enough.

However, Richard finds it still a bit hard for him to do his work after the compression. So he orders you to write a program to make his work easier. Can you help him?

The input contains several test cases, terminated by EOF. The number of test cases does not exceed 10000.
Each test case contains two lines, denote the compressed text and pattern string. The decompressed text and pattern string contain lowercase letter only. The first line contains only lowercase letters (a-z), square brackets ([]) and numbers (0-9), and the second line contains only lowercase letters (a-z). The brackets must be followed with an integer t(1≤t≤231-1)indicating the times the string in the brackets repeat. The brackets won’t be nested.
You can assume the length of the compressed string and pattern string won’t exceed 500.
Please note that for most test cases, the length of the pattern string is relatively very small.

The input contains several test cases, terminated by EOF. The number of test cases does not exceed 10000.
Each test case contains two lines, denote the compressed text and pattern string. The decompressed text and pattern string contain lowercase letter only. The first line contains only lowercase letters (a-z), square brackets ([]) and numbers (0-9), and the second line contains only lowercase letters (a-z). The brackets must be followed with an integer t(1≤t≤231-1)indicating the times the string in the brackets repeat. The brackets won’t be nested.
You can assume the length of the compressed string and pattern string won’t exceed 500.
Please note that for most test cases, the length of the pattern string is relatively very small.

[ab]10aaba
ba

11

1、如果这个区间非压缩的，直接KMP

2、如果这个区间是压缩后的，肯定不能展开暴力KMP。我们只需要统计匹配的起始位置在第一个循环节内的，因为我们在第一个循环节后面添加上p – 1个字符。这样保证了匹配位置在第一个循环节内，然后 便是统计。

注意有些地方的表述，最好用一个较长的串再模拟一下，如[ab]10和[ba]10中查询abab这个串的情况。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>
#define lson step << 1
#define rson step << 1 | 1
using namespace std;
typedef long long LL;
const int N = 5005;
struct Node {
string s;
int cnt;
Node () {}
Node (string _s , int c) :s(_s) , cnt(c) {}
string cat () {
string t = s;
for (int i = 1 ; i < cnt ; i ++)
s = s + t;
cnt = 1;
return s;
}
LL len () {
return (LL)s.size() * cnt;
}
//
string prefix (int l) {
string str = s;
for (int i = 1 ; i < cnt && str.size() < l ; i ++) {
str += s;
}
return str.substr (0 , l);
}
string suffix (int l) {
string str = s;
for (int i = 1 ; i < cnt && str.size() < l ; i ++) {
str += s;
}
return str.substr (str.size() - l , l);
}
}a[N];
char str[N] , pat[N];
int next[N] , idx , l , p;
void get_next (char *s , int l) {
next[0] = -1;
int i = 0 , j = -1;
while (i < l) {
if (j == -1 || s[i] == s[j]) {
i ++; j ++;
next[i] = j;
}
else j = next[j];
}
}
void gao (string s , int tot) {
if (s == "") return ;
if (idx == 0 || s.size() * tot >= p || a[idx - 1].len() >= p) {
a[idx ++] = Node (s , tot);
}
else {
a[idx - 1].cat ();
a[idx - 1].s += Node (s , tot).cat();
}
}
int match (string s , char *t , int p) {
int l = s.size() ;
int i = 0 , j = 0 , ans = 0;
while (i < s.size()) {
if (j == - 1 || s[i] == t[j]) {
i ++; j ++;
if (j == p) {
ans ++;
j = next[j];
}
}
else j = next[j];
}
return ans;
}
int main () {
#ifndef ONLINE_JUDGE
freopen ("input.txt" , "r" , stdin);
freopen ("output.txt" , "w" , stdout);
#endif
while (scanf ("%s %s" , str , pat) != EOF) {
idx = 0;
l = strlen (str);p = strlen (pat);
get_next (pat , p);
string s = "";
int tot = 1;
for (int i = 0 ; i < l ; i ++) {
if (str[i] == '[') {
if (s == "") continue;
gao (s , tot);
s = ""; tot = 1;
}
else if (str[i] == ']') {
tot = 0;
i ++;
while (isdigit(str[i]))
tot = tot * 10 + str[i ++] - '0';
i --;
gao (s , tot);
s = ""; tot = 1;
}
else s += str[i];
}
gao (s , tot);
s = ""; tot = 1;
LL ans = 0;
// for (int i = 0 ; i < idx ; i ++) {
//     cout << a[i].s << " " << a[i].cnt << endl;
// }
for (int i = 0 ; i < idx ; i ++) {
if (a[i].len() < p) continue;
if (a[i].cnt == 1) ans += match (a[i].s , pat , p);
else {
int use = min(a[i].cnt , 1 + (p - 1 + (int)a[i].s.size() - 1) / (int)a[i].s.size());
string s = "";
for (int j = 1 ; j < use ; j ++) {
s += a[i].s;
}
s = a[i].s + s.substr (0 , min ((int)s.size() , p - 1));
int tmp = match (s , pat , p);
ans += (LL)tmp * (a[i].cnt - use + 1);
if (p) {
s = "";
for (int j = 1 ; j < use ; j ++)
s += a[i].s;
ans += match (s , pat , p);
}
}
}
for (int i = 0 ; i < idx - 1 ; i ++) {
s = a[i].suffix (min (a[i].len () , p - 1LL));
if (a[i + 1].len () < p - 1) {
s += a[i + 1].cat ();
if (i + 2 < idx) {
s += a[i + 2].prefix (min (a[i + 2].len () , p - 1 - a[i + 2].len ()));
}
}
else {
s += a[i + 1].prefix (min (a[i + 1].len () , p - 1LL));
}
ans += match (s , pat , p);
}
printf ("%I64d\n" , ans);
}
return 0;
}