Cod sursa(job #1515569)

Utilizator NacuCristianCristian Nacu NacuCristian Data 1 noiembrie 2015 20:46:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

char s[2000020];
char subs[2000020];
int P[2000020];
int lgsubs,lgs;

void citire()
{
    freopen("strmatch.in","r",stdin);
    fgets(s,sizeof(s),stdin);
    fgets(subs,sizeof(subs),stdin);
    lgsubs=strlen(subs)-1;
    lgs=strlen(s)-1;
    for(int i=strlen(subs);i>=0;i--)
        subs[i+1]=subs[i];
    for(int i=strlen(s);i>=0;i--)
        s[i+1]=s[i];
    subs[0]=' ';
    s[0]=' ';
}



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


}

int nr;
vector <int> sol;

void cauta()
{
    int a=0;
    for(int i=1;i<=lgs;i++)
    {
        while(a && s[i]!=subs[a+1])
            a=P[a];
        if(s[i]==subs[a+1])
            a++;
        if(a==lgsubs)
        {
            a=P[a];
            nr++;
            if(nr<=1000)
                sol.push_back(i-lgsubs);
        }


    }
}


int main()
{
    freopen("strmatch.out","w",stdout);
    citire();
    prefix();
    cauta();
    printf("%d\n",nr);
    for(int i=0;i<min(nr,1000);i++)
        printf("%d ",sol[i]);
    return 0;
}