Cod sursa(job #1116137)

Utilizator FasinedJohnny Bravo Fasined Data 22 februarie 2014 12:57:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<cstdio>
#include<cstring>
#include<deque>
#define nx 2000007
using namespace std;
int v[nx],n,m,i,k;
char s[nx],t[nx];
deque<int>d;

void citire()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(s+1);
    n=strlen(s+1);
    gets(t+1);
    m=strlen(t+1);
}

void prefix()
{
    for(i=2;i<=n;i++)
    {
        while(k && s[i]!=s[k+1])k=v[k];
        if(s[k+1]==s[i])k++;
        v[i]=k;
    }
}

void kmp()
{
    k=0;
    for(i=1;i<=m;i++)
    {
        while(k && s[k+1]!=t[i])k=v[k];
        if(s[k+1]==t[i])k++;
        if(k==n)d.push_back(i-n),k=v[k];
    }
}

void afisare()
{
    printf("%d\n",d.size());
    while(!d.empty())printf("%d ",d.front()),d.pop_front();
}

int main()
{
    citire();
    prefix();
    kmp();
    afisare();
    return 0;
}