Cod sursa(job #1300289)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 24 decembrie 2014 12:06:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
//Z-algorithm
#include<bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

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

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

int main()
{
    int i,lena,len,lt,rt,p;
    fin>>(s+1);
    len=lena=strlen(s+1);
    s[++len]='#';
    fin>>(s+len+1);
    i=len+1;
    while (s[i]!=0) i++;
    len=i-1;
    lt=rt=0;
    for (i=2;i<=len;i++)
        if (i>rt)
            {
                lt=rt=i;
                while (rt<=len && s[rt]==s[rt-i+1]) rt++;
                rt--;
                z[i]=rt-lt+1;
            }
        else
            {
                p=i-lt+1;
                if (z[p]<(rt-i+1)) z[i]=z[p];
                else
                    {
                        lt=i;rt++;
                        while (rt<=len && s[rt]==s[rt-i+1]) rt++;
                        rt--;
                        z[i]=rt-i+1;
                    }
            }
    for (i=1;s[i]!='#';i++) ;
    i++;
    for (;i<=len;i++)
        if (z[i]==lena) sol[++sol[0]]=i-lena-2;
    fout<<sol[0]<<"\n";
    for (i=1;i<=min(1000,sol[0]);i++) fout<<sol[i]<<" ";
    fout<<"\n";
    return 0;
}