Cod sursa(job #1409700)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 30 martie 2015 17:49:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>

#define ull unsigned long long
#define ll long long

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N,M,i,k,nrap;
int pi[2000005];
int poz[1005];
char strM[2000005],strN[2000005];

int main()
{
    f>>(strN+1)>>(strM+1);
    M=strlen(strM+1);
    N=strlen(strN+1);
    //cout<<N<<'\n';
    k=0;
    pi[1]=0;
    for (i=2;i<=N;++i)
    {
        while (k>0 && strN[k+1]!=strN[i])
            k=pi[k];
        if (strN[k+1]==strN[i]) // se calculeaza p[i],
            ++k; //  p[i]= lungimea maxima a unui prefix al sirului N,
        pi[i]=k; // care e si sufix pentru prefixul de lungime i;
    }
    k=0;
    for (i=1;i<=M;++i)
    {
        while (k>0 && strN[k+1]!=strM[i])
            k=pi[k];
        if (strN[k+1]==strM[i])
            ++k;
        if (k==N)
        {
            ++nrap;
            if (nrap<=1000)
                poz[nrap]=i-N;
        }
    }
    g<<nrap<<'\n';
    if (nrap>1000)
        nrap=1000;
    for (i=1;i<=nrap;++i)
        g<<poz[i]<<' ';
    f.close();g.close();
    return 0;
}