using namespace std;
typedef long long ll;
vector<ll>pi;
void preFunc(string s)
{
ll len=(ll)s.size();
pi.resize(len+5);
pi[0]=0;
for(ll i=1;i<len;i++){
ll j=pi[i-1];
while((j>0)&&(s[i]!=s[j]))j=pi[j-1];
if(s[i]==s[j])j++;
pi[i]=j;
}
}
int main()
{
ll t;
cin>>t;
ll ck=0;
while(t--){
string s,p;
cin>>s>>p;
ll lenp=p.size();
p+="#";
p+=s;
ll len=p.size();
preFunc(p);
vector<ll>ans;
for(ll i=lenp;i<len;i++){
if(pi[i]==lenp)ans.push_back(i-lenp-lenp+1);
}
ll ct=ans.size();
if(ck==0)ck++;
else cout<<"\n";
if(ct==0)cout<<"Not Found\n";
else{
cout<<ct<<"\n";
ll ck1=0;
for(ll i=0;i<ct;i++){
if(ck1==0)ck1++;
else cout<<" ";
cout<<ans[i];
}
cout<<"\n";
}
}
return 0;
}
Code language: PHP (php)