Cod sursa(job #1474948)

Utilizator dimavascan94VascanDumitru dimavascan94 Data 23 august 2015 11:13:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.43 kb
//#include <stdio.h>
//#include <string.h>
//
//char a[2000005], b[2000005];
//int occ[1005], f[2000005], nOcc = 0, i, j, sizeP, sizeS;
//
//void buildF()
//{
//	f[0] = -1;
//	for (i = 1; i < sizeP; ++i)
//	{
//		j = f[i - 1];
//		while (j != -1 && a[i - 1] != a[j])
//		{
//			j = f[j];
//		}
//		f[i] = j + 1;
//	}
//}
//
//int main()
//{
//	//freopen("strmatch.in", "r", stdin);
//	//freopen("strmatch.out", "w", stdout);
//
//	memset(a, 0, 2000005);
//	memset(b, 0, 2000005);
//
//	scanf("%s%s", a, b);
//
//	sizeP = strlen(a);
//	sizeS = strlen(b);
//
//	buildF();//build the bad suffix good prefix function
//
//	i = j = 0;
//	while (i < sizeS)
//	{
//		if (b[i] == a[j])//the characters match
//		{
//			if (j == sizeP - 1)//found an occurence
//			{
//				occ[nOcc++] = i-j;
//
//				if (nOcc == 1000)//max occurences found
//				{
//					break;
//				}
//
//				j = f[j];
//			}
//			else
//			{
//				i++;
//				j++;
//			}
//		}
//		else//use the bad suffix to find good prefix
//		{
//			if (j == 0)//no good prefix can exist, moving to the next char in string
//			{
//				i++;
//			}
//			else
//			{
//				j = f[j];
//			}
//		}
//	}
//
//	printf("%d\n", nOcc);
//	for (i = 0; i < nOcc; ++i)
//	{
//		printf("%d ", occ[i]);
//	}
//}


#include <stdio.h>
#include <string.h>

#define MAX_LEN 2000000
#define MAX_POS 1000

int pos[MAX_POS];
char a[MAX_LEN + 2];
char b[MAX_LEN + 2];
int pi[MAX_LEN]; // pi[i] = lungimea celui mai lung prefix al S[1..i]
// care este si sufix al S[1..i]

void buildPrefix(char *s, int length) {
	int q = 0;

	pi[0] = 0;
	for (int i = 1; i < length; i++) {
		while ((q > 0) && (s[i] != s[q])) {
			q = pi[q - 1];
		}
		if (s[q] == s[i]) {
			q++;
		}
		pi[i] = q;
	}
}

int main(void) {
	int n, m;
	int q;
	int ans;
	FILE *f = fopen("strmatch.in", "r");

	fgets(a, MAX_LEN + 2, f);
	fgets(b, MAX_LEN + 2, f);
	fclose(f);

	n = strlen(a) - 1;
	m = strlen(b) - 1;

	buildPrefix(a, n);
	q = 0;
	ans = 0;
	for (int i = 0; i < m; i++) {
		while ((q > 0) && (a[q] != b[i])) {
			q = pi[q - 1];
		}
		if (a[q] == b[i]) {
			q++;
		}
		if (q == n) {
			if (ans < MAX_POS) {
				pos[ans] = i;
			}
			ans++;
		}
	}
	f = fopen("strmatch.out", "w");
	fprintf(f, "%d\n", ans);
	if (ans > MAX_POS) {
		ans = MAX_POS;
	}
	for (int i = 0; i < ans; i++) {
		fprintf(f, "%d ", pos[i] - n + 1);
	}
	fclose(f);
	return 0;
}