Cod sursa(job #1927123)

Utilizator CammieCamelia Lazar Cammie Data 14 martie 2017 22:28:00
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>

#define MAXN 2000002

using namespace std;

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

char tmp[MAXN], s[MAXN * 2];
int nn, n, k, pi[MAXN], d[1010], v[1010];

inline void Read()
{
    char c;

    fin >> (s + 1);
    s[0] = '1';
    fin >> c;
    fin >> (tmp + 1);
    tmp[0] = '1';

    nn = strlen(s) - 1;

    n = strlen(tmp) - 1;
}

inline void kmp()
{
    int contor = 0;

    k = 0;
    pi[1] = 0;

    for (int i = 2; i <= nn; i++)
    {
        while (k > 0 && s[i] != s[k + 1])
            k = pi[k];

        if (s[i] == s[k + 1])
            k++;
        pi[i] = k;
    }

    d[1] = 0;
    k = 0;

    if (n > 1000)
        n = 1000;

    for (int i = 2; i <= n; i++)
    {
        while (k > 0 && tmp[i] != s[k + 1])
            k = pi[k];

        if (s[k + 1] == tmp[i])
            k++;
        d[k] = k;

        if (k == nn)
            v[++contor] = i - nn + 1;
    }

    fout << contor << "\n";

    for (int i = 1; i <= contor; i++)
        fout << v[i] << " ";
}

int main ()
{
    Read();
    kmp();

    fin.close(); fout.close(); return 0;
}