Cod sursa(job #1299564)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 23 decembrie 2014 18:41:42
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
//Z-algorithm
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
using namespace std;

const int NMAX=2000005;
const int XMAX=4000005;

char s[XMAX];
int sol[NMAX],z[XMAX];

int main()
{
    int i,lena,len,lt,rt,cnt,p,aux;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin.sync_with_stdio(false);
    cin>>(s+1);
    len=lena=strlen(s+1);
    s[++len]='#';
    cin>>(s+len+1);
    i=len+1;
    while (s[i]!=0) i++;
    len=i-1;
    z[1]=len;
    lt=rt=0;
    for (i=2;i<=len;i++)
        if (i>rt)
            {
                cnt=0;
                while ((i+cnt)<=len && s[cnt+1]==s[i+cnt]) cnt++;
                z[i]=cnt;
                lt=i;
                rt=i+cnt-1;
            }
        else
            {
                p=i-lt+1;
                aux=rt-i+1;
                if (z[p]<aux) z[i]=z[p];
                else
                    {
                        aux=rt+1;
                        while (aux<=len && s[aux]==s[aux-i+1]) aux++;
                        z[i]=aux-i;
                        lt=i;
                        rt=aux-i;
                    }
            }
    for (i=1;s[i]!='#';i++) ;
    i++;
    for (;i<=len;i++)
        if (z[i]==lena) sol[++sol[0]]=i-lena-2;
    cout<<sol[0]<<"\n";
    for (i=1;i<=min(1000,sol[0]);i++) cout<<sol[i]<<" ";
    cout<<"\n";
    return 0;
}