Cod sursa(job #2060656)

Utilizator anisca22Ana Baltaretu anisca22 Data 8 noiembrie 2017 16:28:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define NMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int cnt;
int S[NMAX];
char A[NMAX], B[NMAX];
vector <int> rsp;

void kmp(char sir[], char key[])
{
    int n = strlen(sir + 1);
    int m = strlen(key + 1);

    S[0] = -1;
    S[1] = 0;
    for (int i = 2; i <= m; i++)
    {
        int prv = i - 1;
        char ch = key[i];
        while (S[prv] != -1 && key[S[prv] + 1] != ch)
            prv = S[prv];
        S[i] = S[prv] + 1;
    }

    int lst = 0;
    for (int i = 1; i <= n; i++)
    {
        while (lst != -1)
            if (key[lst + 1] == sir[i])
                break;
            else lst = S[lst];
        lst++;
        if (lst == m)
        {
            rsp.push_back(i - m);
            lst = S[lst];
        }
    }
}

void write()
{
    fout << rsp.size() << "\n";
    vector <int> :: iterator it;
    for (it = rsp.begin(); it != rsp.end(); it++)
    {
        if (++cnt > 1000)
            break;
        fout << *it << " ";
    }
}

int main()
{
    fin >> (A + 1) >> (B + 1);
    kmp(B, A);
    write();
    return 0;
}