Cod sursa(job #1830894)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 17 decembrie 2016 11:19:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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++)
        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;
}