Codeforces Round #299 (Div. 2) D. Tavas and Malekas

http://codeforces.com/contest/535/problem/D

길이가 n인 어떤 문자열 s 가있고, 이 s안에서 k번 등장하는 어떤 패턴 p가 있다.

패턴 p가 등장하는 위치를 오름차순으로 정렬한 sequence 에서 m개의 숫자로 이루어진

임의의 subsequence 를 sub 이라고하자.

입력으로 n, m, p, sub 가 주어질 때, 가능한 원래의 문자열 s의 가짓수를 구하는 문제이다.

\(1 \le n \le 10^6\)

\(0 \le m \le n - |p| + 1\)

\(1 \le |p| \le n\)

우선, 길이 n인 연속된 빈 칸을 생각해 보자 여기에 p가 등장하는 위치에 p를 넣고 난 뒤

빈 칸의 개수를 x라고 할 때 \(26^x\) 를 \(10^9+7\) 로 나눈 나머지를 구하는 문제라고 볼 수 있다.

subsequence 가 나온 이유는 빈칸을 임의의 알파벳으로 채우는 과정에서 새로운 p가 생겨날 수도 있기 때문에 

계산의 간편함을 위함같다는 생각이 든다. 아무튼

먼저 처리해 줘야 할 것이 주어진 sub시퀀스의 원소인 m개의 위치에 대해

패턴 p가 모두 공존 가능(compatible)한지 체크한다. 만약 불가능하다면 0을 출력하고 종료한다.

이 것을 naive 하게 하면 모든 위치에 대해 실제 p를 넣어보면서 다른값이 들어가있으면 불가능하다고

판단할 수가 있는데 물론 \(O(N^2)\) 이다. 그렇다면 어떻게할까? 

패턴 p 에서 prefix 이면서 suffix 인 부분을 찾아보자. 그럼 이 부분이 바로 2개의 p가

겹칠 수 있는 부분이다. 이 부분들로만 겹치면 2개가아니라 여러개를 계속 겹쳐나갈 수가 있다.

이 것을 빠르게 구하는 방법으로 Z algorithm 을 사용해 보자. Z algorithm 에 대한 자세한 설명이 궁금하다면

여기 를 참고하길 바란다. 아무튼 Z Array 를 구한뒤 i + z[i] 가 |p| 와 같은 i들에 있는 z[i] 를 주목하자.

s[i...i+z[i]-1] == s[...z[i]-1] == (prefix 이면서 suffix 인 문자열) 이라는 것을 알 수가 있다.

이 위치 i를 10^6 크기의 배열에 체크를 한다. 

그렇다면 m개의 정렬된 subsequence 의 원소들 사이의 간격이 만약 |p| 보다 작다면

겹칠 수 있는 위치인지 방금 전에 구해놓은 배열을 확인하여 체크한다.

만약 겹칠 수 있는 위치가 아니라면 0을 출력하고 종료. 만약 모든 원소들 사이 간격에

문제가 없으면(겹칠 수 있거나 간격이 |p| 이상) 빈칸의 개수를 세어야 한다.

실제로 m개의 모든 위치에 p를 넣으면 \(O(N^2)\) 이다. 하지만 이미 공존 가능하다는 것을 밝혔으니

겹치는 부분만큼은 넘어가는식으로 하면된다. 구현에 있어 두가지 방법을 떠올렸다.

1. 지금까지 글자를 넣은 마지막 위치 r 을 유지하면서

패턴 p가 등장한 위치들을 하나씩 볼 때 현재 보는 위치가 pos 라면 pos < r 라면 그만큼 건너뛴곳부터 넣고

r < pos 라면 그대로 p를 넣는 식으로 한다.

2. 모든 pos 에 대해 구간 [pos, pos + |p| - 1] 를 만들어서 스위핑한다.

사실 둘다 원리는 비슷하지만 나는 구현이 좀더 간편할 것 같은 2번을 택하였다.

그다음엔 빈칸의 개수만큼 26을 거듭제곱하면 된다.

#include <bits/stdc++.h>
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define fastio() ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const ll infl = 0x3c3c3c3c3c3c3c3c;
 
struct Seg{
    int l, r;
};
int N, M;
string S;
int check[1000003];
int z[1000003];
int L, R;
int p[1000003];
int main() {
    fastio();
    cin >> N >> M >> S;
    for(int i = 0 ; i < M; i++) {
        cin >> p[i];
        p[i]--;
    }
    L = R = -1;
    for(int i = 1; i < sz(S); i++){
        if(i <= R){
            if(z[i - L] < R - i + 1) z[i] = z[i - L];
            else {
                L = i;
                while(R < sz(S) && S[R] == S[R - i]) R++;
                z[i] = R - L; R--;
            }
        }
        else {
            L = R = i;
            while(R < sz(S) && S[R] == S[R - i]) R++;
            z[i] = R - L; R--;
        }
    }
    for(int i = 0 ; i < sz(S); i++) if(z[i] + i == sz(S)) check[i] = 1;
    for(int i = 0 ; i < M - 1; i++) {
        int dif = p[i + 1] - p[i];
        if(dif >= sz(S) || check[dif]) continue;
        return !printf("0");
    }
    vector<Seg> v;
    for(int i = 0 ; i < M; i++) v.pb(Seg{p[i], p[i] + sz(S) - 1});
    int on = 0;
    int last = -1;
    int cnt = 0;
    for(auto sg : v){
        if(last < sg.l) cnt += sg.l - last - 1;
        last = max(last, sg.r);
    }
    cnt += N - last - 1;
    ll ans = 1;
    for(int i = 0 ; i < cnt; i++) ans = (ans * 26) % mod;
    cout << ans;
    return 0;
}