Pagini recente » Cod sursa (job #1704779) | Cod sursa (job #2335145) | Profil M@2Te4i | Statistici Andrei Petrescu (andreipetrescu) | Cod sursa (job #2002976)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f, *g;
int n, m;
char p[2000009];
char t[2000009];
void readFile()
{
f = fopen("strmatch.in", "r");
fgets(p, 2000009, f);
fgets(t, 2000009, f);
n = strlen(p);
m = strlen(t);
p[n --] = 0;
t[m --] = 0;
fclose(f);
}
int urm[2000009];
void getUrm()
{
urm[0] = 0;
int k = -1;
int i;
for(i = 1; i < n; i ++)
{
while(k > 0 && p[k + 1] != p[i])
k = urm[k];
if(p[k + 1] == p[i])
k ++;
urm[i] = k;
}
}
int rez;
int rz[2000009];
void getRez()
{
int k = -1;
int i;
for(i = 0; i < m; i ++)
{
while(k > 0 && p[k + 1] != t[i])
k = urm[k];
if(p[k + 1] == t[i])
k ++;
if(k == n - 1)
rz[++ rez] = i - n + 1;
}
}
void solve()
{
getUrm();
getRez();
}
void printFile()
{
g = fopen("strmatch.out", "w");
fprintf(g, "%d\n", rez);
int i;
for(i = 1; i <= rez; i ++)
fprintf(g, "%d ", rz[i]);
fprintf(g, "\n");
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}