Cod sursa(job #1690334)

Utilizator fulger13Pomirleanu Sebastian fulger13 Data 15 aprilie 2016 00:02:07
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream qu("strmatch.in");
ofstream w("strmatch.out");

char s[2000010],d[2000010];
int n,m,k,pi[2000010],poz[1020];
void prefix()
{
    int i;
    for(i=2;i<=n;i++)
    {
        while(k>0 && ( s[k+1] != s[i] ))
            k=pi[k];
        if(s[k+1]==s[i])
            ++k;
        pi[i]=k;
    }
}

int main()
{int i,j,q=0;;
    qu.getline(s,2000000);
    qu.getline(d,2000000);
    n=strlen(s);
    m=strlen(d);
    for(i=n;i>=1;i--) s[i]=s[i-1];
    for(i=m;i>=1;i--) d[i]=d[i-1];
    s[0]=' ';
    d[0]=' ';
    prefix();
    k=0;
    for(i=1;i<=m;i++)
    {
        while(q && s[q+1]!=d[i])
            q=pi[q];
        if(s[q+1]==d[i])
            ++q;
        if(q==n)
        {
            q=pi[n];
            ++k;
            if(k<=1000)
                poz[k]=i-n;
        }
    }
    int x;
    if(m<1000) x=k;
    else x=1000;
    w<<k<<"\n";
    for(i=1;i<=x;i++) w<<poz[i]<<" ";



    return 0;
}