Classic Quotation

Posted on | In , ,

题目链接

题意

有串和，询问在中挖去后，在其中出现的次数和。

思路

题解讲的很清楚。

说的好像很好写的样子，但是除了上帝没人知道我下面的代码在干什么。
挖个坑，回头把它改一改。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 1e5 + 5;
char s[N], t[105];
int Next[105];

void kmp_pre()
{
	int tlen = strlen(t);
	int i, j;
	j = Next[0] = -1;
	i = 0;
	while (i < tlen)
	{
		while (j != -1 && t[i] != t[j])
			j = Next[j];
		Next[++i] = ++j;
	}
}

ll pref[N], preg[N], suf[N][105], sum[N][105];
ll l, r;
int k, n, m;

ll get()
{
	ll ans = (n - r) * preg[l];
//	dbg(n, l, r, ans);
	for (int i = 0; i < m; i++)
	{
//		dbg(i, sum[l][i], suf[r][i]);
		ans += sum[l][i] * suf[r][i];
	}
	return ans;
}

void solve()
{
	kmp_pre();
	int slen = strlen(s), tlen = strlen(t);
	int i = 0, j = 0;
	pref[0] = 0;
	preg[0] = 0;
	while (i < slen)
	{
		while (j != -1 && s[i] != t[j])
			j = Next[j];
		j++, i++;
		preg[i] = preg[i - 1] + (j == tlen);
		if (j == tlen)
			j = Next[j];
		pref[i] = j;
//		dbg(i, pref[i], preg[i]);
	}
	for (int i = 0; i <= slen; i++)
		for (int j = 0; j <= tlen; j++)
			suf[i][j] = 0;
	for (int i = slen - 2; i >= 0; i--)
		for (int j = tlen - 1; j >= 0; j--)
		{
			int cj = j;
			while (cj != -1 && t[cj] != s[i + 1])
				cj = Next[cj];
			cj++;
			suf[i][j] = suf[i + 1][cj % tlen] + (cj == tlen);
//			dbg(i, j, suf[i][j]);
		}
	for (int i = 1; i < slen; i++)
		preg[i] += preg[i - 1];
	for (int j = 0; j < tlen; j++)
		for (int i = tlen - 2; i >= 0; i--)
			suf[i][j] += suf[i + 1][j];
	for (int i = 0; i <= tlen; i++)
		for (int j = 0; j <= slen; j++)
			sum[j][i] = 0;
	for (int i = 0; i < slen; i++)
		sum[i + 1][pref[i]]++;
	for (int i = 0; i < slen; i++)
		for (int j = 0; j < tlen; j++)
			sum[i][j] += sum[i - 1][j];
	while (k--)
	{
		scanf("%lld%lld", &l, &r);
		l--, r--;
		printf("%lld\n", get());
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d%d", &n, &m, &k);
		scanf("%s", s);
		scanf("%s", t);
		solve();
	}
	return 0;
}
0%