Cod sursa(job #2632370)

Utilizator lucidanescu28Danescu Lucian lucidanescu28 Data 2 iulie 2020 23:19:54
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

void prefix(char *A, int *pi){
    int k = 0;

    for(int i = 1; i < strlen(A); i++){
        while(k && A[k] != A[i]) 
            k = pi[k];
        if(A[k] == A[i]) k++;
        pi[i] = k;
    }
}

void print(vector<int> ans, FILE *fout){
    fprintf(fout, "%ld\n", ans.size());

    for(int i = 0; i < ans.size(); i++)
        fprintf(fout, "%d ", ans[i]);
}

void solve(char *A, char *B, int *pi, FILE *fout){
    int k = 0;
    vector<int> ans;

    for(int i = 0; i < strlen(B); i++){
        while(k > 0 && A[k] != B[i])
            k = pi[k];
        if(A[k] == B[i])
            k++;

        if(k == strlen(A)){
            ans.push_back(i - strlen(A) + 1);
            k = pi[k - 1];    
        }
    }

    print(ans, fout);
}

int main(){
    FILE *fin = fopen("strmatch.in", "r");
    FILE *fout = fopen("strmatch.out", "w");
    char A[2000000], B[2000000];
    int *pi = (int*) calloc(strlen(A), sizeof(int));

    fscanf(fin, "%s%s", A, B);
    prefix(A, pi);
    solve(A, B, pi, fout);
}