Cod sursa(job #1209724)

Utilizator xtreme77Patrick Sava xtreme77 Data 18 iulie 2014 13:42:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
#include <cstring>
#include <vector>

#define pb push_back

const char IN[]="strmatch.in";
const char OUT[]="strmatch.out";
const int MAX = 2000014;

using namespace std;

char sir[MAX],sirsh[MAX];
int p[MAX],n,m,sol;
void prep();
void kmp();
vector <int> ans;
int main()
{
    freopen( IN , "r" , stdin );
    freopen( OUT , "w" , stdout );
    gets(sir+1);
    gets(sirsh+1);
    n = strlen(sir+1);
    m = strlen(sirsh+1);
    prep();
    kmp();
    printf("%d\n",sol);
    for( int i = 0 ; i < (int)ans.size() ; ++ i )
        printf("%d ",ans[i]);
    return 0;
}
void prep()
{
    int k = 0 ;
    for( int i = 2 ; i <= n ; ++ i )
    {
        while(k and sir[i]!=sir[k+1])
            k=p[k];
        if(sir[i]==sir[k+1])++k;
        p[i]=k;
    }
}
void kmp()
{
    int q=0;
    for( int i = 1 ; i <= m ; ++ i ){
        while(q and sirsh[i]!=sir[q+1])
            q=p[q];
        if(sirsh[i]==sir[q+1])++q;
        if( q==n ){
            ++sol;
            if(sol<=1000)
                ans.pb(i-n);
            //else return ;
        }
    }
}