Cod sursa(job #1515556)

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

using namespace std;

char s[10000];
char subs[10000];
int P[1000];
int lgsubs,lgs;

void citire()
{
    freopen("strmatch.in","r",stdin);
    fgets(s,sizeof(s),stdin);
    fgets(subs,sizeof(subs),stdin);
    lgsubs=strlen(subs);
    lgs=strlen(s);
    for(int i=lgsubs;i>=0;i--)
        subs[i]=subs[i-1];
    for(int i=lgs;i>=0;i--)
        s[i]=s[i-1];
    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-1)
        {
            nr++;
            if(nr<=1000)
                sol.push_back(i-a);
            a=P[a];
        }


    }
}


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;
}