Pagini recente » Cod sursa (job #749293) | Cod sursa (job #1118620) | Cod sursa (job #1331228) | Cod sursa (job #874253) | Cod sursa (job #1649537)
#include <fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[2000010],t[2000010];
int pi[2000010];
int k,q,i,slen,tlen,sol;
vector<int> vsol;
int main()
{
fin>>(t+1)>>(s+1);
slen=strlen(s+1);
tlen=strlen(t+1);
/// creeare pi
for(i=2;i<=tlen;++i)
{
while(k>0&&t[k+1]!=t[i])
k=pi[k];
if(t[k+1]==t[i])
k++;
pi[i]=k;
}
for(i=1;i<=slen;++i)
{
while(q>0&&t[q+1]!=s[i])
q=pi[q];
if(t[q+1]==s[i])
q++;
if(q==tlen)
{
sol++;
if(sol<=1000)
{
vsol.push_back(i-tlen);
}
}
}
fout<<sol<<'\n';
for(i=0;i<(int)vsol.size();++i)
fout<<vsol[i]<<" ";
return 0;
}