Instantly share code, notes, and snippets.

@pekempey /a.cpp Secret
Last active Mar 31, 2018

Embed
What would you like to do?
#include <iostream>
#include <vector>
#include <string>
#include <array>
using namespace std;
struct DAWG {
vector<int> suf;
vector<int> len;
vector<array<int, 27>> to;
int last;
DAWG() {
suf.push_back(-1);
len.push_back(0);
to.emplace_back();
last = 0;
}
void append(int c) {
int u = last;
int nxt = suf.size();
to.emplace_back();
suf.push_back(-1);
len.push_back(len[u] + 1);
to[u][c] = nxt;
int s = -1;
while (u != 0 && s == -1) {
u = suf[u];
int v = to[u][c];
if (v == 0) {
to[u][c] = nxt;
} else if (len[u] + 1 == len[v]) {
s = v;
} else {
int w = suf.size();
to[u][c] = w;
to.push_back(to[v]);
len.push_back(len[u] + 1);
suf.push_back(suf[v]);
suf[v] = w;
while (u != 0) {
u = suf[u];
if (to[u][c] == v) {
to[u][c] = w;
} else break;
}
s = w;
}
}
if (s == -1) s = 0;
suf[nxt] = s;
last = nxt;
}
int size() {
return suf.size();
}
};
const int N = 2e5;
DAWG dawg;
int fin[N * 2];
vector<int> g[N * 2];
void dfs(int u) {
fin[u] = dawg.len[u];
for (int v : g[u]) {
dfs(v);
fin[u] = max(fin[u], fin[v]);
}
}
int main() {
string s, t;
cin >> s >> t;
for (char c : s) dawg.append(c - 'a');
dawg.append(26);
for (char c : t) dawg.append(c - 'a');
for (int i = 1; i < dawg.size(); i++) {
g[dawg.suf[i]].push_back(i);
}
dfs(0);
long long ans = 0;
for (int i = 0; i < dawg.size(); i++) {
if (fin[i] <= s.size()) {
ans += dawg.len[i] - dawg.len[dawg.suf[i]];
}
}
cout << ans << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment