Pagini recente » Cod sursa (job #2073620) | Cod sursa (job #71769) | Cod sursa (job #2960912) | Cod sursa (job #2482953) | Cod sursa (job #1190949)
#include <fstream>
#include <cstring>
#define Nmax 2000003
using namespace std;
char subsir[Nmax], sir[Nmax];
int pi[Nmax], poz[Nmax];
int n, m, nr = 0;
int i, j;
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(subsir, Nmax);
f.getline(sir, Nmax);
n = strlen(subsir);
m = strlen(sir);
pi[0]=pi[1]=0;
for (i=1,j=0; i<n; i++)
{
while (j>0 && subsir[i]!=subsir[j])j=pi[j];
if (subsir[i]==subsir[j])j++;
pi[i+1]=j;
}
for (i=j=0; i<m; i++)
{
while (j>0 && subsir[j]!=sir[i]) j=pi[j];
if (subsir[j]==sir[i]) j++;
if (j==n)
{
poz[nr]=i-n+1;
nr++;
j=pi[j];
}
}
g<<nr<<"\n";
for (i=0; i<nr; i++)
g<<poz[i]<<" ";
return 0;
}