Cod sursa(job #1935450)

Utilizator AkrielAkriel Akriel Data 22 martie 2017 13:39:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 2000005;

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

string patern, text, b = " ";

int prefix[N], potriviri;

vector <int> Sol;

int main()
{
    fin >> patern >> text;
    int p = patern.size();
    int t = text.size();
    patern = b + patern;
    text = b + text;
    int q = 0;
    for ( int i = 2 ; i <= p; i++ ){
        while ( q and patern[i] != patern[q+1] )
            q = prefix[q];
        if ( patern[i] == patern[q+1] )
            q++;
        prefix[i] = q;
    }
    q=0;
    for ( int i = 1 ; i <= t; i++ ){
        while ( q and text[i] != patern[q+1] )
            q = prefix[q];
        if ( text[i] == patern[q+1] )
            q++;
        if ( q == p ){
            potriviri++;
            if ( potriviri <= 1000 )
                Sol.push_back(i-p);
        }
    }
    fout << potriviri << "\n";
    for ( auto it : Sol ){
        fout << it << " ";
    }
    return 0;
}