Cod sursa(job #2149238)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 2 martie 2018 13:47:23
Problema Potrivirea sirurilor Scor 34
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N_MAX = 2e6;

string a, b;
int pi[2 * N_MAX + 5];

int nrAns;
vector<int> posAns;

int main()
{
    in >> a >> b;
    b = a + '*' + b;

    int x = 0;
    for(int i = 2; i <= b.length(); i++)
    {
        while(x != 0 && b[x + 1] != b[i])
            x = pi[x];

        x += (b[x + 1] == b[i]);
        pi[i] = x;

        if(pi[i] == a.length() - 1)
        {
            nrAns++;
            if(nrAns <= 1000)
                posAns.push_back(i - 2 * a.length());
        }
    }

    out << nrAns << '\n';
    vector<int>::iterator it;
    for(it = posAns.begin(); it != posAns.end(); it++)
        out << *it << ' ';

    return 0;
}