Pagini recente » Cod sursa (job #2077929) | Cod sursa (job #302775) | Cod sursa (job #1234491) | Cod sursa (job #1593804) | Cod sursa (job #2961548)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int Dim = 2*1e6 + 3;
int n,m,p[Dim+Dim],cnt,k;
vector<int> ans;
string N,M;
int main()
{
cin>>N>>M;
n = N.size();
m = M.size();
if(n>m)
{
cout<<0;
return 0;
}
N += '#';
N += M;
p[0] = -1;
for(int i=1;i<=n+m+1;++i)
{
k = p[i-1];
while(k>=0 && N[k] != N[i-1])
k = p[k];
p[i] = k+1;
if(p[i] == n)
{
cnt++;
if(ans.size()<1000)
ans.push_back(i-n-n+1);
}
}
cout<<cnt<<'\n';
for(auto i : ans)cout<<i<<' ';
return 0;
}