Cod sursa(job #2283022)

Utilizator andru47Stefanescu Andru andru47 Data 14 noiembrie 2018 21:13:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 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()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    char c;
    scanf("%c", &c);
    while (c != '\n')
    {
        a[++n] = c;
        scanf("%c", &c);
    }
    scanf("%c", &c);
    while (c != '\n')
    {
        b[++m] = c;
        scanf("%c", &c);
    }
    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++;}
    }
    
    
    printf("%d\n", cnt);
    for (int i = 1; i<=min(cnt , 1000); ++i)
        printf("%d ", v[i] - n);
    
    printf("\n");
    
    return 0;
}