Cod sursa(job #1515548)

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

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



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


}

int nr;
queue <int> sol;

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

    }
}


int main()
{
    freopen("strmatch.out","w",stdout);
    citire();
    prefix();
    cauta();
    printf("%d\n",nr);
    while(!sol.empty())
    {
        printf("%d ",sol.front());
        sol.pop();
    }
    return 0;
}