Cod sursa(job #1596845)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 11 februarie 2016 14:25:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <string>
#include <vector>
#include <fstream>
#include <string.h>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair

int N;
vector <int> poz;
char A[2000005],B[2000005];
int pref[2000005];

void prep(){
    int q = 0;
    int la = strlen(A+1);
    for(int i = 2;i <= la;i++){
        while(q > 0 && A[q+1] != A[i]){
            q = pref[q];
        }
        if(A[q+1] == A[i]){
            q++;
        }
        pref[i] = q;
    }
}

void kmp(){
    prep();
    int q = 0;
    int la,lb;
    la = strlen(A+1);
    lb = strlen(B+1);
    for(int i = 1;i <= lb;i++){
        while(q > 0 && A[q+1] != B[i]){
            q = pref[q];
        }
        if(A[q+1] == B[i]){
            q++;
        }
        if(q == la){
            N++;
            if(N <= 1000){
                poz.pb(i-la);
            }
        }
    }
}

int main(){
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>A+1;
    f>>B+1;
    kmp();
    g<<N<<'\n';
    for(auto it : poz){
        g<<it<<' ';
    }
}