Cod sursa(job #2086115)

Utilizator serban_ioan97Ciofu Serban serban_ioan97 Data 11 decembrie 2017 14:57:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <cstring>
#define max_dim 2000010

using namespace std;

int nxt[max_dim], positions[1010];
char P[max_dim], T[max_dim];
int n, m, i, q, k;

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    f >> P + 1;
    n = strlen(P + 1);
    f >> T + 1;
    m = strlen(T + 1);

    q = 0;
    nxt[1] = 0;

    for (i = 2; i <= m; i++)
    {
        while (P[i] != P[q+1] && q != 0)
        q = nxt[q];

        if(P[i] == P[q+1])
        ++q;

        nxt[i] = q;
    }

    q=0;
    for (i = 1; i <= n; i++)
    {
        while (T[i] != P[q+1] && q != 0)
        q = nxt[q];
        if (T[i] == P[q+1])
        q++;

        if(q == m)
        {
            k++;
            if(k <= 1000) {
                positions[k] = i - m;
            }
            q = nxt[q];
        }
    }
    g << k <<"\n";

    if(k > 1000) {
        k = 1000;
    }

    for (i = 1; i <= k; i++)
    g << positions[i] << " ";

    return 0;
}