Cod sursa(job #1964942)

Utilizator razvandRazvan Dumitru razvand Data 13 aprilie 2017 20:29:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <queue>
#include <stack>
#include <fstream>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int alf = 52+10;
const int maxS = 2000003;

int prefix[maxS];
vector<int> ans;
int am;

void bfs(string &s) {
    int crr = -1;
    prefix[0] = -1;
    for(int i = 1; i < s.size(); i++) {
        while(crr != -1 && s[crr+1] != s[i])
            crr = prefix[crr];
        if(s[crr+1] == s[i])
            crr++;
        prefix[i] = crr;
    }
}

void dfs(string &s, string &s2) {
    int crr = -1;
    for(int i = 0; i < s.size(); i++) {
        while(crr != -1 && s2[crr+1] != s[i]) {
            crr = prefix[crr];
        }
        if(s2[crr+1] == s[i]) {
            //cout << "TEST " << crr+1 << " " << i << '\n';
            crr++;
        }
        //cout << crr+1 << " " << i << " " << s2[crr+1] << " " << s[i] << '\n';
        if(crr+1 == s2.size()) {
            am++;
            if(ans.size() < 1000)
                ans.push_back(i);
        }
    }
}

int main() {

    string a,b;
    in >> a >> b;
    bfs(a);
    dfs(b, a);
    out << am << '\n';
    for(int i = 0; i < ans.size(); i++)
        out << ans[i]-a.size()+1 << " ";

    return 0;
}