Cod sursa(job #2738726)

Utilizator ViAlexVisan Alexandru ViAlex Data 6 aprilie 2021 11:54:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 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],result[mx],cnt=0;

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;

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

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

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

	out<<cnt<<endl;
	int length=min(cnt,maximum);

	for(i=0;i<length;i++)
		out<<result[i]<<" ";
}
void solve(){
	in>>pattern>>text;	
	preprocess();
	kmp();
}




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