Cod sursa(job #2283031)

Utilizator andru47Stefanescu Andru andru47 Data 14 noiembrie 2018 21:26:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
int n = 0, m = 0, phiA[NMAX], v[1005];
char a[NMAX], b[NMAX];
int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    fin.get(a + 1, NMAX);
    fin.get();
    fin.get(b + 1, NMAX);
    n = (int)strlen(a + 1);
    m = (int)strlen(b + 1);
    a[n + 1] = ' ';
    //construct phiA
    int k = 0;
    phiA[1] = 0;
    for (int i = 2; i<=n; ++i)
    {
        while (k > 0 && a[i] != a[k + 1])
            k = phiA[k];
        if (a[i] == a[k + 1])
            ++k;
        phiA[i] = k;
    }
    
    //construct phiB
    k = 0;
    int cnt = 0;
    for (int i = 1; i<=m; ++i)
    {
        while (k > 0 && a[k + 1] != b[i])
            k = phiA[k];
        if (a[k + 1] == b[i])
            ++k;
        if (k == n){
            if (cnt < 1000)v[++cnt] = i;
            else cnt++;}
    }
    
    
    fout << cnt << '\n';
    for (int i = 1; i<=min(cnt , 1000); ++i)
        fout << v[i] - n << " ";
    
    fout << '\n';
    
    return 0;
}