Pagini recente » Cod sursa (job #1190041) | Cod sursa (job #1190045) | Cod sursa (job #129824) | Cod sursa (job #3256134) | Cod sursa (job #3343703)
#include <fstream>
#include <vector>
#include <cstring>
#define nmax (int)(2e6+1)
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int lps[nmax],n,m,sol;
string s,a;
vector<int>poz;
void get_lps(){
int i=1,len=0;
while(i<n){
if(s[i]==s[len])
lps[i++]=++len;
else if(len==0)
i++;
else
len=lps[len-1];
}
}
void solve(){
int i=0,j=0;
while(j<m){
if(s[i]==a[j])
i++,j++;
else if(i!=0)
i=lps[i-1];
else
j++;
if(i==n){
sol++;
if(sol<=1000)
poz.push_back(j-n);
i=lps[n-1];
}
}
}
signed main()
{
cin>>s>>a;
n=s.size();
m=a.size();
get_lps();
solve();
cout<<sol<<'\n';
for(auto i:poz)
cout<<i<<" ";
return 0;
}