Cod sursa(job #2725328)

Utilizator BalogOctavianBalog Octavian Gheorghe BalogOctavian Data 18 martie 2021 20:01:48
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <sstream>
#include <vector>
#define maxRange 2000001

using namespace std;

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

int m,n, pi[maxRange];
string a,b;

vector <int> v;

void prefix()
{
    int k = 0;
    pi[0] = 0;
    for(int i = 1; i < m; i++)
    {
        while(k && a[k] != a[i]) k = pi[k];
        if(a[k] == a[i]) k++;
        pi[i] = k;
    }
}

int main()
{

    f >> a;
    f >> b;

    m = a.length();
    n = b.length();

    prefix();

    int q = 0;
    for(int i = 0; i < n; i++)
    {
        while(q && a[q] != b[i]) q = pi[q];
        if(a[q] == b[i]) q++;
        if (q == m) q = pi[m-1],v.push_back(i-m+1);
    }

    g << v.size() << '\n';
    for(int i = 0; i < v.size() && i < 1000; i++)
    {
        g << v[i] << ' ';
    }
    return 0;

}