Cod sursa(job #2632503)

Utilizator lucidanescu28Danescu Lucian lucidanescu28 Data 3 iulie 2020 15:38:12
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
	

int pi[2000001];
void prefix(char *A, int *pi){
    int k = 0, size = strlen(A);
	
    for(int i = 2; i <= size; i++){
        while(k && A[k + 1] != A[i]) 
            k = pi[k];
	
        if(A[k + 1] == 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 < 1000; i++)
        fprintf(fout, "%d ", ans[i]);
	
}
	
void solve(char *A, char *B, int *pi, FILE *fout){
    int k = 0, size = strlen(B);
    vector<int> ans;
	
    for(int i = 0; i < size; i++){
        while(k > 0 && A[k + 1] != B[i])
           k = pi[k];
        
        if(A[k + 1] == B[i])
           k++;
	
        if(k == strlen(A) - 1){
           ans.push_back(i - strlen(A) + 2);
           k = pi[k];    
        }
	
    }
	
    print(ans, fout);
}
	
int main(){
    FILE *fin = fopen("strmatch.in", "r");
    FILE *fout = fopen("strmatch.out", "w");
    char A[2000001], B[2000001];

    fscanf(fin, "%s%s", A, B);
    
    for(int i = strlen(A); i > 0; i--)
    	A[i] = A[i - 1];

    prefix(A, pi);	
    solve(A, B, pi, fout);
  
    fclose(fin);
    fclose(fout);
	
}