Pagini recente » Cod sursa (job #2207906) | Cod sursa (job #1270860) | Cod sursa (job #2765614) | Cod sursa (job #1236421) | Cod sursa (job #1155446)
#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 (v[i-1]!=0 && p[i]==p[0]) v[i]=1;
else v[i]=0;
}
void SearchPinS()
{
int i,j=0,SeqStart=0;
for (i=0; i<strlen(s); i++) {
if (s[i]==p[j]) {
//cout<<" Match ! ";
if (j==0) SeqStart++;
++j;
if (j==strlen(p)) {
//cout<<" Found... ";
aparitii[nr++]=SeqStart;
j=v[j-1];
SeqStart=i-j+1;
}
}
else {
if (j==0) SeqStart=i;
else {
if (s[i]==p[v[j-1]]) { j=v[j-1]+1; SeqStart=i-j+1; }
else { j=0; SeqStart=i; }
}
}
//cout<<i<<' '<<j<<' '<<SeqStart<<'\n';
}
}
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(p,sizeof(p));
ChupaChups_p();
f.getline(s,sizeof(s));
SearchPinS();
g<<nr<<'\n';
for (int i=0; i<nr; i++)
g<<aparitii[i]<<' ';
return 0;
}