Pagini recente » Cod sursa (job #3004289) | Cod sursa (job #139032) | Cod sursa (job #125477) | Cod sursa (job #2407700) | Cod sursa (job #2771418)
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
int t, n, m, k, a[300010], q, l, r;
void kmp(int pi[], string &s ){
pi[0]=0;
for(int i=1; i<s.length(); i++){
int j=pi[i-1];
while( (j>0) && (s[j]!=s[i] ) ){
j=pi[j-1];
}
if(s[j]==s[i]){
j++;
}
pi[i]=j;
}
return;
}
int pi[4000005];
pair<int, vector<int>> match(string &t, string &p ){
string s=p+"#"+t;
//cout<<s<<"\n";
//cout<<"ok\n"<<flush;
kmp(pi, s);
//cout<<"ok\n"<<flush;
int lp=p.length();
vector<int> res;
int cnt=0;
for(int i=lp+1; i<s.length(); i++){
if( (pi[i]==lp) ){
cnt++;
if(res.size()<1000){res.pb(i-(lp+1)-(lp-1) );}
// cnt++;
}
}
return {cnt, res};
}
ifstream fin("strmatch.in"); ofstream fout("strmatch.out");
#define cin fin
#define cout fout
int32_t main(){
INIT
string a, b;
cin>>b>>a;
pair<int, vector<int>> rs=match(a, b);
vector<int> res=rs.sc; int cnt=rs.ft;
cout<<cnt<<"\n";
for(int &x:res){
cout<<x<<" ";
}
//cout<<"\n\n";
return 0;
}