Cod sursa(job #1964988)

Utilizator razvandRazvan Dumitru razvand Data 13 aprilie 2017 21:15:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.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+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])
            crr++;
        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;
}