Cod sursa(job #2759672)

Utilizator mihnea_buzoiuMihnea Buzoiu mihnea_buzoiu Data 19 iunie 2021 18:23:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int N = 2e6 + 2;

char a[N];
char b[N];
int lps[N];
int s[1001];

void calc_lps(){
	lps[0] = 0;
	int i = 1, len = 0;

	while (b[i] != 0){
		if (b[i] == b[len]){
			len++;
			lps[i] = len;
			i++;
		}
		else{
			if (len != 0)
				len = lps[len-1];
			else{
				lps[i] = 0;
				i++;
			}
		}
	}

	//for (int i=0; b[i] != 0; i++)
        //printf("%d ", lps[i]);

    //printf("\n");
}

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

    fgets(b, N, stdin);
	fgets(a, N, stdin);

	b[strlen(b)-1] = 0;
    char * enda = &a[strlen(a)-1];
    if (*enda == '\n') *enda = 0;

	calc_lps();

	int i=0, j=0, sn = 0;
	while (a[i] != 0)
	{
		if (a[i] == b[j]){
			i++;
			j++;
		}
		else {
			if (j == 0)
				i++;
			else
				j = lps[j-1];
		}

		if (b[j] == 0){
			if (sn < 1000)
				s[sn] = i - j;
			sn++;
		}
	}

	printf("%d\n", sn);
	for (int i=0; i<sn && i<1000; i++)
		printf("%d ", s[i]);
}
/*
ABA
CABBCABABAB
*/