Cod sursa(job #2738721)

Utilizator ViAlexVisan Alexandru ViAlex Data 6 aprilie 2021 11:48:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>

using namespace std;

const int mx=2e6+100;
const int maximum=1000;

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

string pattern,text;
int lps[mx];

void preprocess(){
	int i=0,j=1;
	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> result;

	while(j<text.length()){
		if(pattern[i]==text[j]){
			i++;
			j++;
		}
		if(i==pattern.length()){
			result.push_back(j-i);

			if(result.size()==maximum){
				break;
			}

			i=lps[i-1];
		}

		if(pattern[i]!=text[j]){

			if(i!=0){
				i=lps[i-1];
			}	
			else j++;
		}
	}

	out<<result.size()<<endl;
	for(int k:result)
		out<<k<<" ";
}
void solve(){
	in>>pattern>>text;	
	preprocess();
	kmp();
}




int main(){
	solve();
	return 0;
}