Algoogle

Algorithm for Programming Contest

AOJ 2444 Substring

Category: AOJ Tag: rolling-hash, string

Substring

問題概要


長さnの文字列sがあり, m個のクエリによって部分文字列の左端と右端の伸縮を行う.
このとき生成される部分文字列の種類の数を答えよ.

解法


m, nが大きいのでナイーブに文字列を生成してsetに入れたりしていると時間もメモリも足りない.
rolling-hash法で文字列を圧縮してO(1)で比較と生成を行えるようにすればよい.

コード


(2444.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
typedef unsigned long long ull;
const ull b = 1000000007;
int N, M, l, r;
string s;
ull powb[300010], shash[300010], S[300010];

int solve(){
    powb[0] = 1;
    rep(i,N) {
        powb[i+1] = powb[i]*b;
        shash[i+1] = shash[i]*b+s[i];
    }
    r = 1;
    rep(i,M){
        cin >> s;
        if(s=="R++") r++;
        else if(s=="R--") r--;
        else if(s=="L++") l++;
        else l--;
        S[i] = shash[r]-shash[l]*powb[r-l];
    }
    sort(S,S+M);
    return unique(S,S+M)-S;
}

signed main(){
    cin >> N >> M >> s;
    cout << solve() << endl;
    return 0;
}

Comments