Pagini recente » Cod sursa (job #1626288) | Cod sursa (job #1206007) | Cod sursa (job #1543257) | Borderou de evaluare (job #1567663) | Cod sursa (job #3005163)
#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]<<" ";
}