Cod sursa(job #2723184)

Utilizator ViAlexVisan Alexandru ViAlex Data 13 martie 2021 19:02:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>

using namespace std;

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

const int mx=2e6+100;
int lps[mx]; 
string pattern,text;

void read(){
	in>>pattern>>text;
}

void preprocess(){
	int i=0,j=1;
	lps[0]=0;

	while(j<pattern.length()){
		if(pattern[i]==pattern[j]){
			i++;
			lps[j]=i;
			j++;
		}
		else{
			if(i>0){
				i=lps[i-1];	
			}		
			else{
				lps[j]=0;
				j++;
			}
		}
	}
}

void kmp(){
	int i=0,j=0;
	vector<int> pos;
	while(j<text.length()){

		if(pattern[i]==text[j]){
			i++;
			j++;
		}	

		if(i==pattern.length()){
			pos.push_back(j-pattern.length());
			i=lps[i-1];
		}

		if(pattern[i]!=text[j]){
			if(i!=0){
				i=lps[i-1];
			}
			else{
				j++;
			}
		}
	}
	out<<pos.size()<<endl;
	for(int k:pos)
		out<<k<<" ";
}

int main(){
	read();
	preprocess();
	kmp();
	return 0;
}