Cod sursa(job #2904869)

Utilizator disinfoion ion disinfo Data 18 mai 2022 12:27:46
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#define MAX 2000005
using namespace std;

int f[MAX];
vector<int> ans;

void compute_table(string b, int n){

	int k;
    for(int i = 1; i <= n - 1; ++i){
        
        k = f[i - 1];
        
        while(k != 0 && b[i] != b[k])
            k = f[k - 1];

        if(b[i] == b[k])
            k += 1;

        f[i] = k;
    }
}

int kmp(string a, string b, int m, int n){
    
    int p = 0, count = 0;
    for(int i = 0; i < m; ++i){
        while(p == n || (p != 0 && a[i] != b[p]))
            p = f[p - 1];
        
        if(a[i] == b[p])
            p += 1;


        if(p == n){
            ans.push_back(i + 1 - n);
            ++count;
        }
    }
    return count;
}


int main(){
	ifstream fin;
	ofstream fout;
	fin.open("strmatch.in");
	fout.open("strmatch.out"); 
	string a, b;
	int m, n;

	getline(fin, b);
	getline(fin, a);
	n = b.size();
	m = a.size();

	compute_table(b, n);
	fout << kmp(a, b, m, n) << "\n";
	for(auto e:ans)
		fout << e << "\n";


}