Pagini recente » Rating Ion Cristian-Razvan (Ion_Cristian_Razvan_324CA) | Cod sursa (job #349833) | Cod sursa (job #1986872) | Cod sursa (job #1385483) | Cod sursa (job #3249841)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> prefix_function(string s) {
int n = (int)s.length();
vector<int> pi(n);
for (int i=1;i<n; i++) {
int j=pi[i-1];
while(j>0 and s[i] != s[j]){
j=pi[j-1];
}
if(s[i] == s[j]){
j++;
}
pi[i]=j;
}
return pi;
}
vector<int> z_function(string s) {
int n = s.size();
vector<int> z(n);
int l=0, r=0;
for(int i=1;i<n;i++) {
if(i<r){
z[i]=min(r-i,z[i-l]);
}
while(i+z[i]<n and s[z[i]]==s[i+z[i]]) {
z[i]++;
}
if(i+z[i]>r) {
l=i;
r=i+z[i];
}
}
return z;
}
int main(){
string a, b;
fin>>a>>b;
b=a+'#'+b;
vector<int> prefix=prefix_function(b), ans1;
int ans=0;
for(int i=1;i<=a.size()+b.size()-1;i++){
if(prefix[i]==a.size()){
ans++;
if(ans1.size()<1000){
ans1.push_back(i-2*a.size());
}
}
}
fout<<ans<<'\n';
for(int i:ans1){
fout<<i<<' ';
}
}