Cod sursa(job #1499047)

Utilizator NacuCristianCristian Nacu NacuCristian Data 10 octombrie 2015 01:54:11
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stdio.h>

using namespace std;

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

void citire()
{
    freopen("strmatch.in","r",stdin);
    fgets(ss,sizeof(ss),stdin);
    fgets(text,sizeof(text),stdin);
    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<strlen(ss);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<=strlen(text)-1;i++)
    {
        while(k && text[i]!=ss[k+1])
            k=P[k];
        if(text[i]==ss[k+1])
            k++;
        if(k>=strlen(ss)-2)
        {
            cont++;
            sol.push_back((i-k));
        }

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

}

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