Pagini recente » Cod sursa (job #911451) | Cod sursa (job #531980) | Cod sursa (job #1847211) | Cod sursa (job #1327604) | Cod sursa (job #3005588)
#include <bits/stdc++.h>
#include <fstream>
#define cin fin
#define cout fout
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
int tata[2000008],lg1,lg2,i2,i,aux,cnt;
char cuv1[2000008],cuv2[2000008];
vector<int>ras;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>cuv1+1;
lg1=strlen(cuv1+1);
cin>>cuv2+1;
lg2=strlen(cuv2+1);
tata[1]=0;
for(i=2;i<=lg1;i++)
{
i2=i-1;
while(cuv1[tata[i2]+1]!=cuv1[i] && i2!=0)
{
i2=tata[i2];
}
if(cuv1[tata[i2]+1]==cuv1[i])
tata[i]=tata[i2]+1;
else
tata[i]=0;
}
aux=0;
for(i=1;i<=lg2;i++)
{
while(cuv1[aux+1]!=cuv2[i] && aux!=0)
{
aux=tata[aux];
}
if(cuv1[aux+1]==cuv2[i])
{
aux=aux+1;
}
if(aux>=lg1)
{
cnt++;
if(cnt<=1000)
ras.push_back(i-lg1);
}
}
cout<<cnt<<'\n';
for(auto i: ras)
{
cout<<i<<" ";
}
return 0;
}