Cod sursa(job #2012511)

Utilizator HumikoPostu Alexandru Humiko Data 18 august 2017 22:43:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

char text[2000001], pattern[2000001];
int pozitie[1001], k, lps[2000001];

void compute_LPS_array (int m)
{
    int len = 0;
    int i = 1;
    while ( i < m )
    {
        if ( pattern[i] == pattern[len] )
        {
            len++;
            lps[i] = len;
            i++;
        }
        else
        {
            if ( len != 0)
                len = lps[len-1];
            else
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void kmp_search (int n, int m)
{
    compute_LPS_array (m);
    int i = 0, j = 0;
    while ( i < n)
    {
        if ( pattern[j] == text[i] )
        {
            i++;
            j++;
        }
        if ( j == m)
        {
            k++;
            pozitie[k] = i - j;
            j = lps[j-1];
        }
        else
            if ( i < n && pattern[j] != text[i])
            {
                if (j != 0)
                    j = lps[j-1];
                else
                    i++;
            }
    }
    fout<<k<<"\n";
    for ( int i = 1; i <= k; ++i )
        fout<<pozitie[i]<<" ";
}

int main()
{
    int n, m;
    fin>>pattern;
    fin>>text;
    n = strlen(text);
    m = strlen(pattern);
    kmp_search (n, m);
}