Pagini recente » Cod sursa (job #2552465) | Cod sursa (job #2827822) | Cod sursa (job #1639523) | Cod sursa (job #1341150) | Cod sursa (job #2859864)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int kmp[4000004];
vector<int>p;
int main()
{
string s,t;
fin>>s>>t;
t=" "+s+t;
s=" "+s;
int n=t.size()-1;
int k=0;
kmp[1]=0;
for(int i=2;i<=n;i++)
{
while(k>0&&t[k+1]!=t[i])
{
k=kmp[k];
}
if(t[k+1]==t[i])
{
k++;
}
kmp[i]=k;
}
int ap=0;
k=0;
for(int i=s.size();i<t.size();i++)
{
while(k&&s[k+1]!=t[i])
{
k=kmp[k];
}
if(s[k+1]==t[i])
{
k++;
}
if(k==s.size()-1)
{
ap++;
if(ap<=1000)
p.push_back(i);
}
}
fout<<ap<<"\n";
for(auto a:p)
{
fout<<a -2*(s.size()-1)<<" ";
}
return 0;
}