Pagini recente » Cod sursa (job #2042642) | Cod sursa (job #2324302) | Cod sursa (job #2097718) | Cod sursa (job #3130070) | Cod sursa (job #1441956)
/*
* File: main.c
* Author: Razvan
*
* Created on May 24, 2015, 12:24 PM
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FILE_IN "strmatch.in"
#define FILE_OUT "strmatch.out"
#define STR_SIZE 1<<21
#define MAX_PRINT 1000
#define MIN(a,b) a <= b ? a : b;
char word[STR_SIZE], line[STR_SIZE];
int i, T[STR_SIZE], wl, ll, M[STR_SIZE], mc;
void computeT(void)
{
T[0] = 0;
T[1] = 1;
for(i=2;i<=wl;++i)
for(T[i] = T[i-1];T[i] <= i-1 && word[i-1] != word[i-1-T[i]];T[i]++);
}
void findMatches(void)
{
int lp=0, wp=0;
while (lp<ll)
{
// printf("%d %d\n", lp, wp);
if(wp < wl && line[lp] == word[wp])
{
if (wp == wl-1)
{
M[mc++] = lp - wl + 1;
}
wp++;
lp++;
}
else
{
if (!wp)
lp++;
wp = wp - T[wp];
}
}
}
/*
*
*/
int main(int argc, char** argv) {
freopen(FILE_IN, "r", stdin);
freopen(FILE_OUT, "w", stdout);
scanf("%s", word);
wl = strlen(word);
scanf("%s", line);
ll = strlen(line);
computeT();
findMatches();
printf("%d\n", mc);
mc = MIN(mc, MAX_PRINT);
for(i=0;i < mc;i++)
printf("%d ", M[i]);
return (EXIT_SUCCESS);
}