Pagini recente » Cod sursa (job #2064161) | Cod sursa (job #881590) | Cod sursa (job #2848015) | Cod sursa (job #2689513) | Cod sursa (job #3005284)
#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<<" ";
}