Cod sursa(job #1199124)

Utilizator IonSebastianIon Sebastian IonSebastian Data 18 iunie 2014 11:38:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int MAX_LUNG = 2000000;

char a[MAX_LUNG+1], b[MAX_LUNG+1];

int prefix[MAX_LUNG+1];
int nrap = 0, k = 0, i;
int appoz[MAX_LUNG+1];
int m, n;
int main()
{
    in >> (a+1) >> (b+1);
    n = strlen(a+1);
    m = strlen(b+1);
    prefix[1] = 0;
    for(i = 2; i <= n; i++)
    {
        while(k > 0 && a[i] != a[k+1])
        {
            k = prefix[k];
        }
        if(a[i] == a[k+1])
        {
            k++;
        }
        prefix[i] = k;
    }
    k = 0;
    for(i = 1; i <= m; i++)
    {
        while(k > 0 && b[i] != a[k+1])
        {
            k = prefix[k];
        }
        if(b[i] == a[k+1])
        {
            k++;
        }
        if(k == n)
        {
            nrap++;
            appoz[nrap] = i-n;
        }
    }
    out << nrap << "\n";
    for(i = 1; i <= nrap && i <= 1000; i++)
    {
        out << appoz[i] << " ";
    }
    in.close();
    out.close();
    return 0;
}