Cod sursa(job #2156805)

Utilizator LuizaPatroescuPatroescu Luiza LuizaPatroescu Data 9 martie 2018 00:17:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax = 2000005;
char a[nmax], b[nmax];
int n, m, urm[nmax];
vector<int> sol;

int main()
{
    ifstream fin ("strmatch.in");
    ofstream fout ("strmatch.out");
    fin >> a >> b;
    n = strlen(a);
    m = strlen(b);
    int k = 0;
    urm[0] = 0;

    for(int i = 1 ; i < n ; ++i)
    {

        while(k>0 && a[k]!=a[i])
        {
            k=urm[k-1];
        }
        if(a[k]==a[i]) k++;
        urm[i]=k;
    }
    k=0;
    for(int j = 0 ; j < m ; j++)
    {

        while(k > 0 && b[j]!=a[k])
        {
            k=urm[k-1];
        }
        if(b[j]==a[k]) k++;
        if(k==n)
        {

            sol.push_back(m-j+1);

        }
    }

    fout << sol.size() << "\n";
    for (int i = 0; i < sol.size() && i < 1000; ++i)
        fout << sol[i] << " ";
    return 0;
}