https://codeforces.com/contest/1090/problem/J
考察有りライブラリ使いまくりで楽しい。
まず文字数を固定します。するとTを少しずつずらした時何通り同じ文字列があるかみたいな問題になります。
こんな感じです。
Tを1文字shift
S:aadaa |
T: aaaaaba|
文字列はaaaaaaba
↓
Tを2文字shift
S:aadaa |
T: aaaaab|a
文字列はaaaaaaab
i文字shiftした時の文字列をDiとしてDiとDjが同じ場合は辺を張るようにしてグラフを作ります。
i < jとして、DiからつながっているDjを考えたいです。するとj-i = lずれた先でも同じということは文字列Tがcyclicになっていることを表します。
よってDiがDjと繋がる条件はTがl周期の文字列でありかつS[i,i+l]=T[0,l]となります。
するとDiとつながっているDjのうちjが最小のものをjmin、jmin-i=lminとすれば、Diはj=i+lmin,i+2*lmin,i+3*lmin...としかつながりません。
さらに、S[i,i+l]=T[0,l]の条件も合わせて考えれば、Diから辺を貼るのはDjminのみで良いことがわかります。
こうして作ったグラフは木なので結局(グラフの頂点数-辺の数)で異なる文字列の数がわかります。
あとは文字数で固定するのではなくshiftの文字数で固定してiterationを回せばできます。
高速化ですが、S[i,i+l]=T[0,l]を判定するのはSuffix array, cyclicになっているかはMP法を使えばいいです。計算量は全体でO(NlogN)で済みます。
int N, M;
string S, T;
int fd(const vi& vec, int a) {
return upper_bound(all(vec), a) - vec.begin();
}
void solve() {
cin >> S >> T;
vi vt = MP(T);
int N = sz(S), M = sz(T);
SA sa;
vi vs;
rep(i, 0, N) vs.pb(S[i] - 'a');
vs.pb(26);
rep(i, 0, M) vs.pb(T[i] - 'a');
sa.init(vs, 27);
vi vec;
rep(i, 1, M + 1) {
if(vt[i]) {
vec.pb(i - vt[i]);
}
}
ll res = 1ll * N * M;
rep(i, 1, N) {
int d = sa.common(i, N + 1);
res -= fd(vec, d);
}
cout << res << "\n";
}
ここで辺