Cod sursa(job #1514977)

Utilizator zertixMaradin Octavian zertix Data 31 octombrie 2015 22:20:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <cstdio>
#define lim 2000010
#include <cstring>
using namespace std;

const int mie=1000;


int nr,i,j,n,m,pref_max[lim],rez[1005];
char pc[lim],ic[lim];

void prefix()
{
    i=0,j=1;
    while (j<n) ///creez prefixul
    {
        if (pc[i]!=pc[j]) ///daca e diferit avem doua cazuri
        {
            if (i==0) ///cand e i=0, mergem pe pozitia urmatoare (adica n-avem o succesiune)
                ++j;
            else
                i=pref_max[i-1]; ///daca i>0, ma retrag pe pozitia de pref_max a elementului anterior
        }
        else
        {
            pref_max[j]=i+1; ///pun in pref_max
            ++j;++i; ///cresc indicii
        }
    }
}

void kmp()
{
    i=0;j=0;
    while (j<m)
    {
        if (ic[j]!=pc[i])

            if (i==0)
                ++j;
            else
                i=pref_max[i-1];
        else
        {
            ++i;++j;
            if (i==n)
            {
                ++nr;
                if (nr<=1000)
                    rez[nr]=j-n;
            }
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",&pc);
    scanf("%s",&ic);

    n=strlen(pc);
    m=strlen(ic);

    if (pc[n-1]=='\n')
        pc[n]=0;
    if (ic[m-1]=='\n')
        ic[m]=0;

    prefix();
    kmp();

    printf("%d\n",nr);
    nr=min(nr,mie);
    for (int i=1;i<=nr;++i)
        printf("%d ",rez[i]);

    return 0;
}