Pagini recente » Cod sursa (job #1697738) | Cod sursa (job #1217511) | Cod sursa (job #2934723) | Cod sursa (job #1092007) | Cod sursa (job #1413486)
#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 i,k,nr,n,m;
vector<int> sol;
int main()
{
fin>>(t+1)>>(s+1);
k=0;
n=strlen(t+1);
for(i=2;i<=n;++i)
{
while(k>0&&t[k+1]!=t[i])
k=pi[k];
if(t[k+1]==t[i])
k++;
pi[i]=k;
}
n=strlen(s+1);
m=strlen(t+1);
k=0;
for(i=1;i<=n;++i)
{
while(k>0&&t[k+1]!=s[i])
k=pi[k];
if(t[k+1]==s[i])
k++;
if(k==m)
{
nr++;
sol.push_back(i-m);
k=pi[k];
}
}
fout<<nr<<'\n';
k=0;
for(i=0;i<nr;++i)
{
k++;
fout<<sol[i]<<" ";
if(k==1000)
{
return 0;
}
}
return 0;
}