TopCoder

Thumb tmwe
gamegame
林煜翔的粉絲 Fan of William Lin

User's AC Ratio

75.0% (9/12)

Submission's AC Ratio

39.1% (9/23)

Description

給你一個字串 $T$,以及很多字串 $P$。

對於每個 $P$ 請輸出 $P$ 在 $T$ 中出現過幾次。

請給出 edit distance 與下列程式碼不超過 $1$ 的解。

#include <bits/stdc++.h>
#define int long long

using namespace std;

int M = 998244353;
int x = 137;

int h[10005], xp[10005];

void Hash(string& s) {
    h[s.length()] = 0;
    for(int i = s.length()-1 ; i >= 0 ; i--) {
        h[i] = (h[i+1]*x%M + s[i]-'a'+1)%M;
    }
}

int gethashvalue(int L, int len) {
    return (h[L] - h[L+len]*xp[len]%M + M)%M;
}

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    xp[0] = 1;
    for(int i = 1 ; i < 10005 ; i++) xp[i] = xp[i-1]*x%M;

    int t, q; cin >> t;
    while(t--) {
        string s, p; cin >> s;
        Hash(s);
        cin >> q;
        while(q--) {
            cin >> p;
            int ph = 0;
            for(int i = p.length()-1 ; i >= 0 ; i--) {
                ph = (ph*x%M + p[i]-'a'+1)%M;
            }
            int cnt = 0;
            for(int i = 0 ; i+p.length()-1 < s.length() ; i++) {
                if(gethashvalue(i, p.length()) == ph) cnt++;
            }
            cout << cnt << '\n';
        }
    }
}

Input Format

第一行有個數字代表有幾組測資。

每組測資的第一行是字串 $T$,

第二行有個數字 $Q$ 代表有幾個詢問,

接下來的 $Q$ 行每行都個一個字串 $P$。

$T$、$P$ 都是由小寫字母所組成,長度不會超過 $10000$。

Output Format

對於每個詢問輸出 $P$ 在 $T$ 中出現過幾次。

Sample Input

2
abcdefefef
3
bcd
ef
efef
ccodegeass
2
akira
cc

Sample Output

1
3
2
0
1

Hints

Problem Source

TIOJ 1306

Subtasks

For Testdata: 0 ~ 1, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144