Cod sursa(job #2639639)

Utilizator ionita786Ionita Daniel ionita786 Data 3 august 2020 12:27:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define Nmax 2000005
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

string a,b;
int pi[Nmax], poz[2000],nr,n,m;
void prefix()
{
    int q = 0;
    pi[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        while(q && a[q+1] != a[i])
           q = pi[q];
        if(a[q+1] == a[i])
            ++q;
        pi[i] = q;
    }
}
void pattern()
{
    int q = 0;
    for(int i = 1; i <= m; ++i)
    {
        while(q && a[q+1] != b[i])
           q = pi[q];
        if(a[q+1] == b[i])
            ++q;
        if(q == n)
        {
            q = pi[n];
            ++nr;
            if(nr <= 1000)
                poz[nr] = i - n;
        }
    }
}
int main()
{
    in >> a >> b;
    n = a.size();
    m = b.size();
    for(int i = n; i > 0; --i) a[i] = a[i-1];
    for(int i = m; i > 0; --i) b[i] = b[i-1];
    a[0] = ' ';
    b[0] = ' ';
    prefix();
    pattern();
    out << nr << '\n';
    for(int i = 1; i <= nr; ++i)
        out << poz[i] << " ";
    return 0;
}