Cod sursa(job #2566165)

Utilizator rusu.ralucaRusu Raluca rusu.raluca Data 2 martie 2020 19:15:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream> 
#include <fstream>
#include <vector>
#include <cstring>

#define N 2000005

using namespace std;

/*  
    Se dau doua siruri A si B formate din litere mici si mari ale alfabetului englez si din cifre. 
    Se cere gasirea tuturor aparitiilor sirului A ca subsecventa a sirului B.
*/ 

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

char A[N], B[N];
int pi[N], v[1004], nr, a, b;

void kmp1(){
    int k = 0;
    for(int i = 1; i <= b; ++i){
        while(k && A[k + 1] != B[i])
            k = pi[k];
        if(A[k + 1] == B[i]) 
            ++k;
        if(k == a){
            ++nr;
            if(nr <= 1000)
                v[nr] = i;
        }
    }

}

void kmp(){
    int k = 0;
    for(int i = 2; i <= a; ++i){
        while(k && A[k + 1] != A[i])
            k = pi[k];
        if( A[k + 1] == A[i])
            ++k;
        pi[i] = k;
    }
}

int main(){
    in >> (A+1);
    in >> (B+1);
    a = strlen(A+1);
    b = strlen(B+1);

    kmp();
    kmp1();

    out << nr << '\n';
    if(nr>1000) nr=1000;
    for(int i = 1; i <= nr; ++i)
        out << v[i] - a << ' ';
    return 0;
    
      
}