Cod sursa(job #711184)

Utilizator mihai995mihai995 mihai995 Data 11 martie 2012 16:02:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <cstring>
using namespace std;

const int N=2000002;
char a[N],text[N];
int p[N],rez[N];

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

void prefix()
{
    p[0]=-1;
    for (int i=2;a[i];i++)
        for (int j=p[i-1];j>=0;j=p[j])
            if (a[j+1]==a[i])
            {
                p[i]=j+1;
                break;
            }
}

int len(char a[],char b[])
{
    int i;
    for (i=0;a[i] && a[i]==b[i];i++);
    return i;
}

void match()
{
    int size=strlen(a+1);
    for (int i=1,j;text[i];i+=j-p[j])
    {
        j=len(text+i,a+1);
        if (j==size)
            rez[++rez[0]]=i-1;
    }
}

int main()
{
    in>>a+1>>text+1;
    prefix();
    match();
    out<<rez[0]<<"\n";
    rez[0]=min(rez[0],1000);
    for (int i=1;i<=rez[0];i++)
        out<<rez[i]<<" ";
    out<<"\n";
    return 0;
}