Cod sursa(job #1499055)

Utilizator NacuCristianCristian Nacu NacuCristian Data 10 octombrie 2015 02:20:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stdio.h>

using namespace std;

char text[2000020],ss[2000020];
int P[2000020],m,n;

void citire()
{
    freopen("strmatch.in","r",stdin);
    fgets(ss,sizeof(ss),stdin);
    fgets(text,sizeof(text),stdin);
    m=strlen(ss)-1;
    n=strlen(text)-1;
    for(int i=strlen(ss);i>=0;i--)
        ss[i+1]=ss[i];
    for(int i=strlen(text);i>=0;i--)
        text[i+1]=text[i];
    ss[0]=' ';
    text[0]=' ';
}

void prefix()
{
    int a=0;
    for(int i=2;i<=m;i++)
    {
        while(a && ss[a+1]!=ss[i])
            a=P[a];
        if(ss[i]==ss[a+1])
            a++;
        P[i]=a;
    }
}

vector <int> sol;
int cont;

void cautare()
{
    for(int i=1,k=0;i<=n;i++)
    {
        while(k && text[i]!=ss[k+1])
            k=P[k];
        if(text[i]==ss[k+1])
            k++;
        if(k==m)
        {
            k=P[k];
            cont++;
            if(cont<1000)
            sol.push_back((i-m));
        }

    }
    freopen("strmatch.out","w",stdout);
    printf("%d\n",cont);
    for(int i=0;i<min(cont,1000);i++)
        printf("%d ",sol[i]);

}

int main()
{
    citire();
    prefix();
    cautare();
    return 0;
}