Pagini recente » Cod sursa (job #2630518) | Cod sursa (job #2549949) | Cod sursa (job #2037097) | Cod sursa (job #1936543) | Cod sursa (job #3040641)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lps[2000001];
string ahoy,corasick;
vector<int> rez;
int main()
{
int n,m,i,j,len=0,c=0;
fin>>ahoy>>corasick;
n=ahoy.size();
lps[0]=0;
i=1;
while(i<n)
{
while(ahoy[i]!=ahoy[len]&&len>0)
{
len=lps[len-1];
}
if(ahoy[i]==ahoy[len])
len++;
lps[i++]=len;
}
m=corasick.size();
i=0,j=0;
while(i<m)
{
while(corasick[i]!=ahoy[j]&&j>0)
j=lps[j-1];
if(corasick[i]==ahoy[j])
j++;
i++;
if(j==n)
{
c++;
if(c<=1000)
rez.push_back(i-n);
}
}
fout<<c<<'\n';
for(i=0;i<rez.size();i++)
fout<<rez[i]<<' ';
return 0;
}