Pagini recente » Cod sursa (job #2151348) | Cod sursa (job #1743892) | Cod sursa (job #1144789) | Cod sursa (job #1673559) | Cod sursa (job #2002982)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f, *g;
int n, m;
char p[2000099];
char t[2000099];
void readFile()
{
f = fopen("strmatch.in", "r");
fgets(p, 2000099, f);
fgets(t, 2000099, f);
n = strlen(p);
m = strlen(t);
p[n --] = 0;
t[m --] = 0;
int i;
for(i = n; i >= 1; i --)
p[i] = p[i - 1];
for(i = m; i >= 1; i --)
t[i] = t[i - 1];
fclose(f);
}
int urm[2000099];
void getUrm()
{
urm[1] = 0;
int k = 0;
int i;
for(i = 2; 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 = 0;
int i;
for(i = 1; i <= m; i ++)
{
while(k > 0 && p[k + 1] != t[i])
k = urm[k];
if(k + 1 < 0)
printf("ERROE\n");
if(p[k + 1] == t[i])
k ++;
if(k == n)
{
//k = urm[k];
rez ++;
///1945626
// if(rez >= 137630)
// printf("%d ", i - n);
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;
}