Pagini recente » Cod sursa (job #2665668) | Cod sursa (job #1971859) | Cod sursa (job #1393875) | Cod sursa (job #3184955)
#include<fstream>
#include<string>
#include<vector>
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
int p[2000001];
std::vector<int>ans;
std::string seq, word;
long long size, nr;
void getPrefix()
{
int i=0, j=-1;
p[0]=-1;
while(i<size)
{
while(j>=0 && seq[i]!=seq[j])
j=p[j];
++i;
++j;
p[i]=j;
}
}
void solve()
{
long long size1=word.size();
int i=0, j=-1;
while(i<size1)
{
while(j>=0 && word[i]!=seq[j])
j=p[j];
++i;
++j;
if(j==size)
{
++nr;
ans.push_back(i-size);
}
}
fout<<nr<<'\n';
for(int index=0; index<nr && index<1000; ++index)
fout<<ans[index]<<' ';
}
int main()
{
fin>>seq>>word;
size=seq.size();
getPrefix();
solve();
return 0;
}