Pagini recente » Cod sursa (job #2420348) | Cod sursa (job #1979000) | Cod sursa (job #768675) | Cod sursa (job #2348134) | Cod sursa (job #1168287)
#include<fstream>
#include<string>
#include<vector>
#include<algorithm>
#define Nmax 2000010
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
vector<int>sol;
int p[Nmax]={-1, 0}, i, j, c;
void prefix()
{
i=0;
for(j=1;j<A.size();++j)
{
while(A[i]==A[j] && j<A.size())
{
i++,j++;
p[j]=p[j-1]+1;
}
i=0;
if(A[i]==A[j])
{
i++;
p[j+1]=1;
}
}
}
void solve()
{
int k=0;
c=0;
for(i=0;i<B.size();++i)
{
while(k>0 && A[k]!=B[i])
k=p[k];
if(A[k]==B[i])k++;
if(k==A.size())
{
c++;
if(c<=1000)
sol.push_back(i-A.size()+1);
}
}
}
int main()
{
fin>>A>>B;
prefix();
solve();
fout<<c<<'\n';
for(i=0;i<min(c,1000);++i)
fout<<sol[i]<<' ';
return 0;
}