Cod sursa(job #3005163)

Utilizator BadHero112Ursu Vasile BadHero112 Data 16 martie 2023 19:53:26
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 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=200001;
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;
			if(s[j]==s[i]){
				l=i;
				r=i;
				j++;
				while(j+i<m+n+1&&s[i+j]==s[j]){
					r++;
					j++;
				}
				Z[i]=r-l+1;
			}
		}
		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&&A.size()<=1000){
		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]<<" ";
}