Cod sursa(job #1965051)

Utilizator andytosaAndrei Tosa andytosa Data 13 aprilie 2017 21:52:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a, b;
int n, m, pi[2000010], i, j, nr, sol[1010];
int main()
{
    fin >> a >> b;
    n = a.size();
    m = b.size();
    i = 1; j = 0;

    for(i = 1; i < n; i++){
        while(j > 0 && a[j] != a[i])
            j = pi[j - 1];
        if(a[j] == a[i])
            j++;
        pi[i] = j;
        //cout << pi[i] << ' ';
    }
    j = 0;
    for(i = 0; i < m; i++){
        while(j > 0 && a[j] != b[i])
            j = pi[j - 1];
        if(a[j] == b[i])
            j++;
        if(j == n){
            nr++;
            j = pi[j - 1];
            if(nr <= 1000) sol[nr] = i - n + 1;
        }
    }

    fout << nr << '\n';
    for(i = 1; i <= min(nr, 1000); i++)
        fout << sol[i] << ' ';
    return 0;
}