Pagini recente » Cod sursa (job #2776825) | Cod sursa (job #3129340) | Cod sursa (job #2827985) | Cod sursa (job #2492824) | Cod sursa (job #1156660)
#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;
int j=0;
for (int i=1; i<strlen(p); i++) {
while (j>0 && p[i]!=p[j]) j=v[j-1];
if (p[i]==p[j]) ++j;
v[i]=j;
}
}
void SearchPinS()
{
int i,j=0;
for (i=0; i<strlen(s); i++) {
while (j>0 && s[i]!=p[j]) j=v[j-1];
if (s[i]==p[j]) {
//cout<<" Match ! ";
++j;
if (j==strlen(p)) {
//cout<<" Found... ";
aparitii[nr++]=i-j+1;
j=v[j-1];
}
}
//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;
}