Cod sursa(job #1515552)

Utilizator NacuCristianCristian Nacu NacuCristian Data 1 noiembrie 2015 20:26:07
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 <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);

}



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;
vector <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)
        {
            nr++;
            if(nr<=1000)
                sol.push_back(i-a+1);
            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);
    for(int i=0;i<min(1000,nr);i++)
        printf("%d ",sol[i]);
    return 0;
}