Cod sursa(job #2277185)

Utilizator matei8787Matei Dobrea matei8787 Data 5 noiembrie 2018 21:04:15
Problema Potrivirea sirurilor Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[2000000],b[2000000];
int ans1[2000000],c[2000000];
int main()
{
    char h;
    in>>a;
    in>>b;
    in.get(h);
    int q=0,n,l,ans=0;
    n = strlen(b);
    l = strlen(a);
    c[1] = 0;
    for ( int i = 0 ; i <= n ; i++ ){
        while ( q && b[i-1] != a[q] )
            q = c[q];
        if ( b[ i - 1 ] == a [ q ] )
            q++;
        c[i] = q;
    }
    for ( int i = 0 ; i <= n - 1 ; i++ ){
        while ( q && b[i-1] != a[q] )
            q = c[q];
        if ( b[ i - 1 ] == a [ q ] )
            q++;
        if ( q == l ){
            q = c[l];
            ans++;
            ans1[i-l] = 1;
        }
    }
    out<<ans<<'\n';
    for ( int i = 1 ; i <= n ; i++ ){
        if ( ans1[i] != 0 )
            out<<i<<" ";
    }
    return 0;
}