Cod sursa(job #1964890)

Utilizator razvandRazvan Dumitru razvand Data 13 aprilie 2017 19:32:11
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#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;
}