Cod sursa(job #1844359)

Utilizator FredyLup Lucia Fredy Data 9 ianuarie 2017 22:29:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

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

#define lim 2000100
char pattern[lim],text[lim],sum[2*lim],nr;
int pref[2*lim];
int n,m,l;
vector <int> v;

void formare()
{
    strcat(sum,".");
    strcat(sum,pattern);
    strcat(sum,"*");
    strcat(sum,text);
    n=strlen(pattern);
    m=strlen(text);
    l=strlen(sum)-1;

}

void prefix_function()
{
    int k;
    for(int i=2; i<=l; i++)
    {
        k=pref[i-1];
        while(k && sum[k+1]!=sum[i])    k=pref[k];
        if(sum[k+1]==sum[i])    k++;
        pref[i]=k;
        if(k==n && i>n+1)    v.push_back(i-2*n-1);
    }

}

void afisare()
{
    fout<<v.size()<<'\n';
    for(auto it:v)
    {
        fout<<it<<' ';
        if(++nr==1000)  return;
    }

}


int main()
{
    fin>>pattern>>text;

    formare();
    prefix_function();
    afisare();

    fin.close();
    fout.close();
    return 0;
}