Cod sursa(job #1804900)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 13 noiembrie 2016 11:03:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<bits/stdc++.h>
#define NMAX 2000040
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[NMAX], sol[NMAX], s, n, m;
char a[NMAX], b[NMAX];
int main ()
{
    f>> a + 1 >> b + 1;
    n = strlen (a + 1);
    m = strlen (b + 1);
    int k = 0;
    for (int i = 2; i <= n; i++)
    {
        while (k && a[k + 1] != a[i])
            k = pi[k];
        if (a[k + 1] == a[i])
            k++;
        pi[i] = k;
    }
    k = 0;
    for (int i = 1; i <= m; i++)
    {
        while (k && a[k + 1] != b[i])
            k = pi[k];
        if (a[k + 1] == b[i])
            k++;
        if (k == n)
        {
            s++;
            if (s <= 1000)
                sol[s] = i - k;
            k = pi[k];
        }
    }
   g<< s << "\n" ;
    for (int i = 1; i <= min (1000,s); i++)
        g<< sol[i] << " ";
    return 0;
}