Cod sursa(job #2155309)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 7 martie 2018 19:44:43
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int rez[1001];
int p = -1;

void construire_pi(char *c, int lungime, int *pi)
{

    pi[1] = 0;
    pi[0] = 0;
    int i = 1;
    int k = 0;
    while(i < lungime)
    {
        if(c[i] == c[k])
        {
            k++;
            pi[i] = k;
            i++;
        }
        else
        {
            if(k != 0)
            {
                k = pi[k - 1];
            }
            else
            {
                pi[i] = 0;
                i++;
            }
        }
    }
}

int kmp(char *c1 , char *c2)
{
    // c1 - pattern     c2 - text
    int i = 0 , j = 0, ct = 0;

    int M = strlen(c1);
    int N = strlen(c2);

    int pi[M];

    construire_pi(c1,M,pi);

    while(i < N)
    {
        if(c1[j]== c2[i])
        {
            i++;
            j++;
        }
        if(j == M )
        {
            if(p < 1000)
                rez[++p] = i;
            ct++;
            j = pi[j - 1];
        }
        else if(i < N&& c1[j] !=c2[i])
        {
            if(j != 0)
            {
                j = pi[j - 1];
            }
            else
                i++;
        }

    }
    return ct;
}

int main()
{
    char *c1;
    char *c2;
    fin.get(c1,sizeof(c1));
    fin.get();
    fin.get(c2,sizeof(c2));
    fout << kmp(c1,c2);
    for(int i = 0 ; i < p; i++)
        fout << rez[i] << " ";

    return 0;
}