Cod sursa(job #3005284)

Utilizator BadHero112Ursu Vasile BadHero112 Data 16 martie 2023 20:58:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=2000001;
using namespace std;

int n,m,Z[2*maxn+1];
string N,M;



int main(){
	ifstream cin("strmatch.in");
	ofstream cout("strmatch.out");
	cin>>M;
	cin>>N;
	n=N.length();
	m=M.length();
	string s=M+'$'+N;
	int i=1,l=0,r=0;
	while(i<n+m+1){
		if(i>r){
			int j=0;
			l=i;
			r=i;
			while(i+j<n+m+1&&s[j]==s[i+j]){
				j++;
				r++;
			}
			Z[i]=r-l;
			r--;
		}
		else{
			int k=i-l;
			if(Z[k]<r-i+1){
				Z[i]=Z[k];
			}
			else{
				l=i;
				while(r<n+1+m&&s[r-l]==s[r])r++;
				Z[i]=r-l;
				r--;
			}
		}
		i++;
	}
	vector<int> A;
	i=m;
	while(i<n+m+1){
		if(Z[i]==m)A.push_back(i-m);
		i++;
	}
	cout<<A.size()<<endl;
	for(int i=0;i<A.size();i++)cout<<A[i]-1<<" ";
}