Pagini recente » Cod sursa (job #2531580) | Cod sursa (job #262355) | Cod sursa (job #2671426) | Cod sursa (job #320095) | Cod sursa (job #1156460)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char p[2000000];
char s[2000000];
int v[2000000];
int aparitii[1000000];
int nr=0;
void ChupaChups_p()
{
v[0]=0;
for (int i=1; i<strlen(p); i++)
if ( p[i]==p[v[i-1]]) v[i]=v[i-1]+1;
else if (p[i]==p[0]) v[i]=1;
else v[i]=0;
}
void SearchPinS()
{
int i,j=0;
for (i=0; i<strlen(s); i++) {
if (s[i]==p[j]) {
//cout<<" Match ! ";
++j;
if (j==strlen(p)) {
//cout<<" Found... ";
aparitii[nr++]=i-j+1;
j=v[j-1];
}
}
else {
while (j>0 && s[i]!=p[j]) j=v[j-1];
if (s[i]==p[j]) ++j;
}
//cout<<i<<' '<<j<<' '<<'\n';
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>p;
ChupaChups_p();
f>>s;
SearchPinS();
g<<nr<<'\n';
for (int i=0; i<nr; i++)
g<<aparitii[i]<<' ';
return 0;
}