Cod sursa(job #2155412)

Utilizator mihailescu_eduardMihailescu Eduard-Florin mihailescu_eduard Data 7 martie 2018 20:38:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <cstring>

using namespace std;

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

#define NMax 2000005
char c1[NMax];
char c2[NMax];

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

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 )
        {
            rez[++p] = i - j;
            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()
{

    fin.getline(c1,sizeof(c1),'\n');
    fin.getline(c2,sizeof(c2));
    int ct = kmp(c1,c2);
    fout << ct << endl;
    for(int i = 0 ;i <= min(p, 1000); i++)
        fout << rez[i] << " ";



    return 0;
}