Pagini recente » Cod sursa (job #2838247) | Cod sursa (job #2554941) | Cod sursa (job #1790621) | Cod sursa (job #2802563) | Cod sursa (job #1615627)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
int p[2000001];
vector<int> sol;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
void prefix(string s)
{
int k=0;
for(int i=1;i<s.size();i++)
{
while(k>0 && s[k]!=s[i]) k=p[k-1];
if(s[k]==s[i]) k++;
p[i]=k;
}
}
int main()
{
string s,x;
cin>>x>>s;
prefix(x);
int k=0;
for(int i=1;i<s.size();i++)
{
while(k>0 && x[k]!=s[i]) k=p[k-1];
if(x[k]==s[i]) k++;
if(k==x.size())sol.push_back(i-x.size()+1);
}
cout<<sol.size()<<'\n';
for(int i=0;i <min(int(sol.size()),1000);i++)
cout<<sol[i]<<' ';
return 0;
}