lightoj1255

maksyuki 发表于 oj 分类，标签: 字符串-KMP

27 8月 2015

1255 - Substring Frequency

InputA string is a finite sequence of symbols that are chosen from an alphabet. In this problem you are given two non-empty strings A and B, both contain lower case English alphabets. You have to find the number of times B occurs as a substring of A.

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with two lines. First line contains A and second line contains B. You can assume than 1 ≤ length(A), length(B) ≤ 10⁶.

Output

For each case, print the case number and the number of times B occurs as a substring of A.

Sample Input

Output for Sample Input

4axbyczdabcabcabcabcabc

abc

aabacbaabbaaz

aab

aaaaaa

Case 1: 0Case 2: 4Case 3: 2Case 4: 5

Note

Dataset is huge, use faster I/O methods.

题目类型：KMP

算法分析：这是一道使用KMP算法求解模式串在目标串中数量的题目，思路是如果模式串匹配成功，则将模式串指针j回溯至Next[j]，看看能不能再一次匹配

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 1000000 + 66;

char pattern[maxn], target[maxn];

int suffix[maxn];

void Build ()
{
	int len = strlen (pattern);

	suffix[0] = -1;
	suffix[1] = 0;
	int k = 0;

	int i;
	for (i = 2; i <= len; i++)
	{
		while (k >= 0 && pattern[i-1] != pattern[k])
			k = suffix[k];

		suffix[i] = ++k;
	}
}

int KMP ()
{
	int len_pattern = strlen (pattern);
	int len_target = strlen (target);
    int cnt = 0;

	int i = 0, j = 0;
    while (i < len_target)
    {
        if (pattern[j] == target[i] || j == -1)
        {
            i++;
            j++;
        }

        else
            j = suffix[j];

        if (j == len_pattern)
        {
            cnt++;
            j = suffix[j];
        }
    }

return cnt;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 1000000 + 66;

char pattern[maxn], target[maxn];

int suffix[maxn];

void Build ()

{

int len = strlen (pattern);

suffix[0] = -1;

suffix[1] = 0;

int k = 0;

int i;

for (i = 2; i <= len; i++)

{

while (k >= 0 && pattern[i-1] != pattern[k])

k = suffix[k];

suffix[i] = ++k;

}

int KMP ()

{

int len_pattern = strlen (pattern);

int len_target = strlen (target);

int cnt = 0;

int i = 0, j = 0;

while (i < len_target)

{

if (pattern[j] == target[i] || j == -1)

{

i++;

j++;

}

else

j = suffix[j];

if (j == len_pattern)

{

cnt++;

j = suffix[j];

}

return cnt;

}

lightoj1215

lightoj1259

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1255

Output

Sample Input

Output for Sample Input

Note

分类目录

标签云

书签

近期评论