Pagini recente » Cod sursa (job #227325) | grind_baraje_liceu | Cod sursa (job #1837688) | Cod sursa (job #2131092) | Cod sursa (job #1083566)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define cout g
string sablon,text;
int l[2000000],v[2000000];
void calculeaza_l()
{
int i,k;
for(i=2; i<=sablon.length()-1; ++i)
{
k=l[i-1];
while (k && sablon[k+1]!=sablon[i]) k=l[k];
if(sablon[k+1]==sablon[i]) k++;
l[i]=k;
}
}
int main()
{
f>>sablon>>text;
sablon=' '+sablon;
text=' '+text;
//cout<<sablon[3];
calculeaza_l();
int k=0,i,nr(0);
//cout<<text.length();
for(i=1; i<=text.length()-1; i++)
{
while(k && sablon[k+1]!=text[i]) k=l[k];
if(sablon[k+1]==text[i])++k;
if(k==sablon.length()-1)
{
v[++nr]=i-sablon.length()+1;
}
}
cout<<nr<<'\n';
for(i=1;i<=min(1000,nr);++i)cout<<v[i]<<' ';
return 0;
}