Cod sursa(job #1498736)

Utilizator NacuCristianCristian Nacu NacuCristian Data 9 octombrie 2015 00:15:53
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#include <stdio.h>

using namespace std;

char text[10000],ss[1000];
int P[1000];

void citire()
{
    ifstream fin("strmatch.in");
    fin.getline(ss,1000);
    fin.getline(text,10000);
}

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

vector <int> sol;
int cont;

void cautare()
{
    int n=strlen(ss),m=strlen(text),k=0,i=0,j=0;
    while(m-k>=n)
    {
        while(j<=n && ss[j]==text[i])
            i++,j++;
        if(j>=n)
        {
            cont++;
            sol.push_back(k);
        }
        if(P[j-1]>0)
            k=i-P[j-1];
        else
        {
            if(i==k)
                i++;
        k=i;
        }
        if(j>0)
            j=P[j-1];
    }
    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;
}