Cod sursa(job #3249606)

Utilizator vlad7654vladimir manescu vlad7654 Data 17 octombrie 2024 10:41:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int z[4000005];
void zfunc(string s){
    z[0]=0;
    int l=0;
    int r=0;
    for(int i=1;i<s.size();i++){
        if(i<=r){
            z[i]=min(z[i-l],r-i);
        }
        while(i+z[i]<s.size() and s[z[i]]==s[i+z[i]]){
            z[i]++;
        }
        if(i+z[i]-1>r){
            l=i;
            r=i+z[i]-1;
        }
    }
}
int main(){
    string a,b;
	fin>>a>>b;
	b=a+"@"+b;
	zfunc(b);
	int ans=0;
	vector<int> sol;
	for(int i=a.size();i<b.size();i++){
		if(z[i]==a.size()){
			ans++;
			if(sol.size()<1000){
				sol.push_back(i-a.size()-1);
			}
		}
	}
	fout<<ans<<'\n';
	for(int i:sol){
		fout<<i<<' ';
	}
}