Cod sursa(job #895450)

Utilizator the@EyE@Postavaru Stefan the@EyE@ Data 27 februarie 2013 11:29:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define INF 2000002

using namespace std;

char text[INF],s[INF];
int p[INF],k,lt,ls,max;
vector<int> ind;

void pref()
{
    p[0]=-1;
    int k=-1;
    for(int i=1;i<ls;++i)
    {
        while(k>-1&&s[i]!=s[k+1])k=p[k];
        if(s[i]==s[k+1])++k;
        p[i]=k;
    }
}

void kmp()
{
    int k=-1;
    for(int i=0;i<lt;++i)
    {
        while(k>-1&&text[i]!=s[k+1])k=p[k];
        if(text[i]==s[k+1])++k;
        if(k==ls-1){ind.push_back(i-k);k=p[k];
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    gets(s);
    gets(text);
    ls=strlen(s);
    lt=strlen(text);
    pref();
    kmp();
    printf("%d\n",ind.size());
    for(int i=0;i<ind.size()&&i<1000;++i)printf("%d ",ind[i]);
    return 0;
}