March 17, 2020

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);
}
}

Posted by
xiaodao

Category: 日常