Cod sursa(job #1514818)

Utilizator zertixMaradin Octavian zertix Data 31 octombrie 2015 17:18:43
Problema Potrivirea sirurilor Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <cstdio>
#define lim 2000010
#include <cstring>
using namespace std;

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

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

    n=strlen(pc);
    m=strlen(ic);
    pc[n]='0';
    ic[n]='0';
    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
        }
    }

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

            if (j==0)
                ++i;
            else
                j=pref_max[j-1];
        else
        {
            ++i;++j;
            if (j==n)
            {
                ++nr;
                if (nr<=1000)
                    rez[nr]=i-n;
            }
        }
    }
    printf("%d\n",nr);
    for (int i=1;i<=nr;++i)
        printf("%d ",rez[i]);

    return 0;
}