Cod sursa(job #1164386)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 2 aprilie 2014 00:42:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

const int NMax = 2000010;

int sol;
vector <int> ans;
int N, M;
char A[NMax], B[NMax];
int pi[NMax];

void Read()
{
    ifstream f("strmatch.in");
    f >> (A + 1);
    f >> (B + 1);
    f.close();
    N = strlen(A + 1);
    M = strlen(B + 1);
    f.close();
}

void Pi()
{
    int k;
    pi[1] = 0;
    k = 0;
    for (int i = 2; i <= N; ++ i)
    {
        while (k > 0 && A[k + 1] != A[i])
            k = pi[k];
        if (A[k + 1] == A[i])
            ++k;
        pi[i] = k;
    }
}

void KMP()
{
    int k;
    k = 0;
    for (int i = 1; i <= M; ++ i)
    {
        while (k > 0 && A[k + 1] != B[i])
            k = pi[k];
        if (A[k+1] == B[i])
            ++k;
        if(k == N)
        {
            if (ans.size() < 1000)
                ans.push_back(i - N);
            ++ sol;
        }
    }
}

void Write()
{
    ofstream g("strmatch.out");
    g << sol << "\n";
    for (vector <int> :: iterator it = ans.begin(); it != ans.end(); ++ it)
        g << *it << " ";
    g << "\n";
    g.close();
}

int main()
{
    Read();
    Pi();
    KMP();
    Write();
    return 0;
}