Cod sursa(job #1997571)

Utilizator horiacoolNedelcu Horia Alexandru horiacool Data 4 iulie 2017 21:01:22
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <list>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

char N[2000003],M[2000003];
int n,m,P[2000003];

int nrpoz;
list<int>poz;

void Prefix()
{
    int i = 0,j = 1;

    while( j < n )
    {
        if( N[i] == N[j] )
        {
            P[j] = i+1;
            i++;
            j++;
        }
        else
        {
            if( i == 0 )
            {
                P[j] = 0;
                j++;
            }
            else
            {
                i = P[i-1];
            }
        }
    }
}

void KMP()
{
    int i = 0,j = 0;

    while( j < m )
    {
        if( N[i] == M[j] )
        {
            i++;
            j++;

            if( i == n )
            {
                nrpoz++;
                if( nrpoz < 1001 )
                poz.push_back(j-n);

                i = P[i-1];
            }
        }
        else
        {
           if( i == 0 )
           {
               j++;
           }
           else
           {
               i = P[i];
           }
        }
    }
}

int main()
{
    f>>N>>M;
    n = strlen(N);
    m = strlen(M);

    Prefix();
    KMP();

    g<<nrpoz<<'\n';
    for(list<int>::iterator it = poz.begin() ; it != poz.end() ; it++)
        g<<*it<<' ';

    return 0;
}