Cod sursa(job #2061410)

Utilizator CatapaPap Catalin Catapa Data 9 noiembrie 2017 10:51:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

const int Dim = 2000005;
char pattern[Dim], text[Dim];
int k, pi[Dim],rez[Dim],n,m,dim;

void prefix()
{
    n = strlen(pattern+1);
   k = 0;
    for(int i=2; i<=n; i++)
    {
        while(k>0 && pattern[k+1]!=pattern[i])
            k = pi[k];
        if(pattern[k+1]==pattern[i])
            k+=1;
        pi[i] = k;
    }
}

void kmp()
{
    m = strlen(text+1);
  k=0;
    for(int i=1; i<=m; i++)
    {
        while(k>0 && pattern[k+1]!=text[i])
            k = pi[k];
        if(pattern[k+1]==text[i])
            k+=1;
        if(k==n)
        {
            k = pi[k];
            dim+=1;
            if(dim <= 1000)
                rez[dim] = i-n;
        }
    }
}




int main()
{
    f >> pattern+1 >> text+1;
    prefix();
    kmp();
    g << dim << "\n";
    dim = min(dim ,1000);
    for(int i=1; i<=dim; i++)
        g << rez[i] << ' ';
    return 0;
}