Cod sursa(job #2071740)

Utilizator HoriaDruliacHoria Druliac HoriaDruliac Data 20 noiembrie 2017 22:44:10
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char N[1000],H[1000];
int S[1000],vec[2000];
int n,h,f,cont;
int main()
{
    fin>>N+1;
    fin>>H+1;
    n=strlen(N+1);
    h=strlen(H+1);
    /// se construieste sirul S
    S[0]=-1;
    S[1]=0;
    for (int i=2; i<=n; i++)
    {
        /// se calculeaza S[i]
        int p;
        char c;
        p=S[i-1];
        c=N[i];
        while (1)
        {
            if (p==-1)
                break;
            if (N[p+1]==c)
                break;
            p=S[p];
        }
        S[i]=p+1;
    }
    /// KMP
    f=0;
    for (int i=1; i<=h; i++)
    {
        char c;
        c=H[i];
        /// bucla while
        int s=f;
        while (1)
        {
            if (s==-1)
                break;
            if (N[s+1]==c)
                break;
            s=S[s];
        }
        f=s+1;
        if (f==n)
        {
            cont++;
            if(cont<=1000)
                vec[cont]=i-n;
            f=S[f];
        }
    }
    fout<<cont<<"\n";
    if(cont>1000)
        cont=1000;
    for(int i=1; i<=cont; i++)
        fout<<vec[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}