Submission #223207

#	Time	Username	Problem	Language	Result	Execution time	Memory
223207		lyc	Trener (COCI20_trener)	C++14	55 / 110	2090 ms	5844 KiB

trener

#include <bits/stdc++.h>
using namespace std;

#define SZ(x) (int)(x).size()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int MX_N = 55;
const int MX_K = 1505;

const int MOD = 1e9+7;

int N, K;
string S[MX_N][MX_K];

int dp[MX_N][MX_K];

vector<int> build_table(string W) {
    vector<int> T(W.length()+1);
    int pos = 1;    // the current position we are computing in T
    int cnd = 0;    // the zero-based index in W of the next character of the current candidate substring

    T[0] = -1;

    while (pos < (int)W.length()) {
        if (W[pos] == W[cnd])
            T[pos] = T[cnd];
        else {
            T[pos] = cnd;
            cnd = T[cnd]; // (to increase performance)
            while (cnd >= 0 and W[pos] != W[cnd]) {
                cnd = T[cnd];
            }
        }
        pos = pos + 1, cnd = cnd + 1;
    }
    T[pos] = cnd; // (only need when all word occurrences searched)

    return T;
}

bool search(string S, string W, vector<int>& T) {
    int P[S.length()];
    int nP;

    int j = 0;
    int k = 0;
    
    nP = 0;

    while (j < (int)S.length()) {
        if (W[k] == S[j]) {
            j = j + 1;
            k = k + 1;
            if (k == (int)W.length()) {
                // (occurrence found, if only first occurrence is needed, m <- j - k  may be returned here)
                P[nP] = j - k, nP = nP + 1;
                k = T[k]; // (T[length(W)] can't be -1)
            }
        }
        else {
            k = T[k];
            if (k < 0) {
                j = j + 1;
                k = k + 1;
            }
        }
    }

    return nP > 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    FOR(i,1,N){
        FOR(j,1,K) cin >> S[i][j];
    }

    FOR(j,1,K) dp[N][j] = 1;
    RFOR(i,N-1,1){
        FOR(j,1,K){
            dp[i][j] = 0;

            vector<int> T = build_table(S[i][j]);

            FOR(k,1,K) {
                if (search(S[i+1][k], S[i][j], T)) {
                    //cout << i << " " << j << " :: " << i+1 << " " << k << endl;
                    dp[i][j] += dp[i+1][k];
                    if (dp[i][j] >= MOD) dp[i][j] -= MOD;
                }
            }
        }
    }

    int ans = 0;
    FOR(i,1,K){
        ans += dp[1][i];
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
}

Compilation message (stderr)

trener.cpp: In function 'bool search(std::__cxx11::string, std::__cxx11::string, std::vector<int>&)':
trener.cpp:43:9: warning: variable 'P' set but not used [-Wunused-but-set-variable]
     int P[S.length()];
         ^

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55