Cod sursa(job #2277169)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 5 noiembrie 2018 20:51:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int P[2000055],i,q,nrsol,sol[2000055];
char v[2000055],t[2000055];
void kmp(int n){
    P[1]=0;
    for(i=2;i<=n;i++){
        q=P[i-1];
        while(q&&v[i]!=v[q+1])
            q = P[q];
        if(v[i]==v[q+1])
            q++;
        P[i]=q;
        }
    }

int main()
{
    f>>v+1;
    f>>t+1;
    int n= strlen(t+1);
    int len=strlen(v+1);
    int q=0;
    kmp(len);
    for(i=1;i<=n;i++){
        while( q && t[i] != v[q+1])
            q=P[q];
        if(t[i]==v[q+1])
            q++;
        if(q == len){
            q = P[len];
            nrsol ++;
            sol[nrsol]=i-len;
        }

    }
    g<<nrsol<<'\n';
    for(i=1;i<=min(nrsol,1000);i++)
        g<<sol[i]<<" ";
    return 0;
}