Cod sursa(job #1298022)

Utilizator MariusGeantaMarius Geanta MariusGeanta Data 22 decembrie 2014 14:59:48
Problema Potrivirea sirurilor Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.36 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int pos[1000];
int pre[2000000];

int basicSearch(char *pattern, char *str)
{
	char *p;
	int len = strlen(pattern);
	int lenStr = strlen(str);
	int num = 0;

	for (p = str; p - str <= lenStr - len + 1; p++) {
		if (!strncmp(p, pattern, len) && num < 1000) {
			pos[num++] = p - str;
		}
	}

	return num;
}

void prefix(char *p)
{
	int len = strlen(p);
	int x;
	int k = 0;

	pre[0] = 0;
	for (x = 1; x < len; x++) {
		while (k > 0 && p[k] != p[x])
			k = pre[k - 1];

		if (p[k] == p[x])
			k++;

		pre[x] = k;
	}
}

/**
 * TODO
 */
int kmp(char *pattern, char *str)
{
	int num = 0;
	int m = strlen(pattern);
	int n = strlen(str);
	int d;
	int k = 0;

	prefix(pattern);
	for (d = 0; d < n; d++) {
		while (k > 0 && pattern[k] != str[d])
			k = pre[k - 1];

		if (pattern[k] == str[d])
			k++;

		if (k == m) {
			if (num < 1000) {
				pos[num] = d - k + 1;
			}
			num++;
			k = pre[k - 1];
		}
	}

	return num;
}

int main()
{
	char *pattern;
	char *str;
	int n, i;

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	pattern = malloc(2000000);
	str = malloc(2000000);

	scanf("%s", pattern);
	scanf("%s", str);

	kmp(pattern, str);

//	n = basicSearch(pattern, str);
	n = kmp(pattern, str);

	printf("%d\n", n);
	if (n > 1000)
		n = 1000;
	for (i = 0; i < n; i++)
		printf("%d ", pos[i]);

	return 0;
}