Pagini recente » Cod sursa (job #1330945) | Cod sursa (job #2471049) | Cod sursa (job #2169031) | Cod sursa (job #1902648) | Cod sursa (job #2002978)
#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[1009];
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)
{
rez ++;
if(rez <= 1000)
rz[rez] = i - n + 1;
}
}
}
void solve()
{
getUrm();
getRez();
}
void printFile()
{
g = fopen("strmatch.out", "w");
fprintf(g, "%d\n", rez);
int af;
if(rez >= 1000)
af = 1000;
else
af = rez;
int i;
for(i = 1; i <= af; i ++)
fprintf(g, "%d ", rz[i]);
fprintf(g, "\n");
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}