某岛

… : "…アッカリ~ン . .. . " .. .
March 17, 2020

HDU 6740. MUV LUV EXTRA

namespace KMP{
    void get_pi(const char P[], int n, int pi[]){
        for (int i = 1, j = pi[0] = -1; i < n; ++i){
            while (j >= 0 && P[i] != P[j+1]) j = pi[j];
            if (P[i] == P[j+1]) ++j;
            pi[i] = j;
        }
        //REP(i, n) cout << pi[i] << " "; cout << endl;
    }
    
    int run(const char T[], int n, const char P[], int m, const int pi[]){
        int cnt = 0; for (int i = 0, j = -1; i < n; ++i){
            while (j >= 0 && T[i] != P[j+1]) j = pi[j];
            if (T[i] == P[j+1]) ++j;
            if (j == m - 1) ++cnt, j = pi[j];
        }
        return cnt;
    }
} //using namespace KMP;

const int N = int(1e7) + 9;
char T[N], P[N]; int pi[N];
int Tn, Pn;

int main() {
    
#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    
    LL a, b; while (~scanf("%lld %lld", &a, &b)) {
        scanf("%s", T); Tn = int(strlen(T)); Pn = 0;
        DWN(i, Tn, 0) {
            if (T[i] == '.') break;
            P[Pn++] = T[i];
        }
        P[Pn] = 0;
        KMP::get_pi(P, Pn, pi);
        LL z = -INFF; REP(i, Pn) checkMax(z, a*(i+1) - b*(i-pi[i]));
        printf("%lld\n", z);
    }
}