Cod sursa(job #2198939)

Utilizator LivcristiTerebes Liviu Livcristi Data 25 aprilie 2018 21:49:56
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define NUM 2000005
char a[NUM];
char b[NUM];
int pi[NUM], poz[1024];
int n, la, lb;
using namespace std;
void prefix()
{
    int k = 0;
    pi[1] = 0;
    for(int i = 2; i < la; ++i)
    {
        while(a[k + 1] != a[i] && k > 0)
            k = pi[k];
        if(a[k + 1] == a[i])
            k++;
        pi[i] = k;
    }
}
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f >> a >> b;
    la = strlen(a);
    lb = strlen(b);
    for(int i = la; i >= 1; --i)
        a[i] = a[i-1];
    for(int i = lb; i >= 1; --i)
        b[i] = b[i-1];
    la++, lb++;
    prefix();
    int k = 0;
    for(int i = 1; i < lb; ++i)
    {
        while(a[k + 1] != b[i] && k > 0)
            k = pi[k];
        if(a[k + 1] == b[i])
            k++;
        if(k == la - 1)
        {
            n++;
            if(n <= 1000)
                poz[n] = i - k;
            k = pi[k];
        }
    }
    g << n << "\n";
    if(n > 1000)
        n = 1000;
    for(int i = 1; i <= n; ++i)
        g << poz[i] << " ";
    f.close();
    g.close();
}