Pagini recente » Cod sursa (job #1897212) | Cod sursa (job #1840051) | Cod sursa (job #1920387) | Cod sursa (job #1264790) | Cod sursa (job #2480828)
#include <fstream>
#include <iostream>
#include <cstring>
#define lungimeMax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[lungimeMax], b[lungimeMax];
int p[lungimeMax], n, m, poz[1005], nr;
void formPref()
{
int pi = 0;
for(int i = 2; i <= n; i++)
{
while(pi > 0 && a[i] != a[pi+1])
pi = p[pi];
if(a[i] == a[pi+1])
++pi;
p[i]=pi;
}
}
void afis()
{
for(int i=0; i<=n; i++)
cout<<p[i]<<' ';
}
void matching()
{
int pi = 0;
for(int i = 1; i <= m; i++)
{
while(pi > 0 && b[i] != a[pi+1])
pi = p[pi];
if(b[i] == a[pi+1])
++pi;
if(pi == n)
{
nr++;
if(nr <= 1000)
poz[nr]=i-n;
}
}
}
int main()
{
f.getline(a+1, lungimeMax);
f.getline(b+1, lungimeMax);
//cout<<a+1<<'\n'<<b+1;
n=strlen(a+1);
m=strlen(b+1);
formPref();
//afis();
matching();
g<<nr<<'\n';
for(int i = 1; i <= nr; i++)
g<<poz[i]<<' ';
return 0;
}