Pagini recente » Cod sursa (job #2185950) | Cod sursa (job #231149) | Cod sursa (job #1676798) | Cod sursa (job #2137042) | Cod sursa (job #1964890)
#include <iostream>
#include <queue>
#include <stack>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int alf = 52;
const int maxS = 2000003;
int g[maxS][alf];
int viz[maxS];
int f[maxS];
vector<int> ans[maxS];
stack<int> antib;
int tim = 1;
void build(string &s) {
int p = 0;
int crr = 1;
while(p != s.size()) {
if(g[crr][s[p]-'A'] == 0)
g[crr][s[p]-'A'] = ++tim;
crr = g[crr][s[p]-'A'];
p++;
}
}
void bfs() {
int crr = 1;
queue<int> q;
for(int i = 0; i < alf; i++) {
if(g[1][i] != 0) {
f[g[1][i]] = 1;
q.push(g[1][i]);
} else
g[1][i] = 1;
}
while(!q.empty()) {
crr = q.front();
antib.push(crr);
q.pop();
for(int i = 0; i < alf; i++) {
if(g[crr][i] != 0) {
int F = f[crr];
while(g[F][i] == 0)
F = f[F];
f[g[crr][i]] = g[F][i];
q.push(g[crr][i]);
}
}
}
}
void dfs(string &s) {
int p = 0;
int crr = 1;
while(p != s.size()) {
viz[crr]++;
if(p != 0 && ans[crr].size() < 1000)
ans[crr].push_back(p-1);
while(g[crr][s[p]-'A'] == 0)
crr = f[crr];
crr = g[crr][s[p]-'A'];
p++;
}
viz[crr]++;
if(ans[crr].size() < 1000)
ans[crr].push_back(p-1);
}
void antibfs() {
int crr = 1;
while(!antib.empty()) {
crr = antib.top();
antib.pop();
for(int i = 0; i < ans[crr].size(); i++) {
if(ans[f[crr]].size() >= 1000)
continue;
ans[f[crr]].push_back(ans[crr][i]);
}
viz[f[crr]] += viz[crr];
}
}
int main() {
string a,b;
in >> a >> b;
build(a);
bfs();
dfs(b);
antibfs();
out << viz[tim] << '\n';
for(int i = 0; i < ans[tim].size(); i++)
out << ans[tim][i]-a.size()+1 << " ";
return 0;
}