Cod sursa(job #2188198)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 26 martie 2018 23:42:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

const string fisier = "strmatch";
string a, b;
int urm[2000003], k, cnt;
vector<int> sol;

int main()
{
    ifstream fin (fisier+".in");
    ofstream fout (fisier+".out");
    fin >> a >> b;
    k = 0;
    urm[0] = 0;
    for (int i = 1; i < a.length(); ++i){
        while(k > 0 && a[k] != a[i])
            k = urm[k-1];
        if(a[k] == a[i])
            ++k;
        urm[i] = k;
    }
    k = 0;
    for (int i = 0; i < b.length(); ++i){
        while(k > 0 && a[k] != b[i])
            k = urm[k-1];
        if(a[k] == b[i])
            ++k;
        if(k == a.length()){
            ++cnt;
            if(cnt <= 1000)
                sol.push_back(i-k+1);
        }
    }
    fout << cnt << "\n";
    for (vector<int>::iterator it = sol.begin(); it != sol.end(); ++it)
        fout << *it << " ";
    return 0;
}