Cod sursa(job #1830896)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 17 decembrie 2016 11:20:50
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define nmax 2000000+5

using namespace std;

// we're looking for W in S
char S[nmax], W[nmax];
int m, n;
int prefix[nmax];

vector<int> sol;

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin >> W+1; n = strlen(W+1);
    cin >> S+1; m = strlen(S+1);

    int i, j;
    // form prefix table

    j = 0;
    prefix[0] = 0;
    for (i = 2; i <= n; i++)
    {
        while (j > 0 && W[j+1] != W[i])
            j = prefix[j];

        if (W[i] == W[j+1])
            j++;

        prefix[i] = j;
    }

    j = 0;
    for (i = 1; i <= m; i++)
    {
        while (S[i] != W[j+1] && j > 0)
            j = prefix[j];
        if (S[i] == W[j+1])
            j++;
        if (j == n)
            sol.push_back(i-n+1);
    }

    cout << sol.size() << "\n";

    for (i = 0; i < sol.size() && i < 1000; i++)
        cout << sol[i]-1 << " ";
    //for (i = 1; i <= n; i++)
      //  cout << W[i] << '\t';
    //cout << '\n';
    //for (i = 1; i <= n; i++)
      //  cout << prefix[i] << '\t';
    return 0;
}