/* par20_ex4_x1.c SJ */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <omp.h>



int readFileToString(char *fileName, char **contents);
double ltime();
char * randomString(int n, int nchar);
void printsubstring(char *A, int start, int count);
int longestRepeatingSubstring(const char *A, int len, int *Rpos1, int *Rpos2);
int longestRepeatingSubstring_mpi(const char *A, int len, int *Rpos1, int *Rpos2);



int main(int argc, char *argv[]) {
	char *input;
	int N = 50; // 10000;	// string length
	int maxchar = 2;	// character set size

	int pos1, pos2, len;

	double starttime, endtime, seqtime, partime;

	if (argc > 1)
		N = atoi(argv[1]);
	if (argc > 2)
		maxchar = atoi(argv[2]);

	input = randomString(N, maxchar);

	if (N <= 80)
		printf("Input: %s\n", input);

	starttime = ltime();
	len = longestRepeatingSubstring(input, N, &pos1, &pos2);
	endtime = ltime();
	seqtime = endtime-starttime;

	printf("\nLongest repeating (seq): len=%d, ", len);
	printf("pos1=:%d (", pos1);
	if (len < 80) printsubstring(input, pos1, len);
	printf(") pos2=%d: (", pos2);
	if (len < 80) printsubstring(input, pos2, len);
	printf(")\n");
	printf("Sequential %.6lf s\n", seqtime);


	starttime = ltime();
	len = longestRepeatingSubstring_mpi(input, N, &pos1, &pos2);
	endtime = ltime();
	partime = endtime-starttime;

	printf("\nLongest repeating (par): len=%d, ", len);
	printf("pos1=:%d (", pos1);
	if (len < 80) printsubstring(input, pos1, len);
	printf(") pos2=%d: (", pos2);
	if (len < 80) printsubstring(input, pos2, len);
	printf(")\n");
	printf("Parallel %.6lf s\n", partime);
	printf("Speedup: %.2f\n", seqtime/partime);

	free(input);

	return 0;
}

void printsubstring(char *A, int start, int count) {
	int i;
	for (i = start; i<start+count; i++)
		putchar(A[i]);
}


/**
 * Generate random string of length n
 * @param n  string length
 * @param nchar how many different characters to use
 * @return the new string, of NULL of n<0
 */
char * randomString(int n, int nchar) {
	int i;
	char *s;
	char base = '0';
	if (n < 0)
		return NULL;
	if (nchar > 26)
		nchar = 26;
	if (nchar > 10)
		base = 'a';
	s = (char*)malloc(n+1);
	for (i = 0; i < n; i++)
		s[i] = base + rand()%nchar;
	s[n] = '\0';
	return s;
}


/**
 * Longest repeating substring of string A.
 * The substrings may overlap partially.
 * @param A input string
 * @param len  length of A (redundant)
 * @param Rpos1 pointer to which the first starting position is stored (or -1 if no duplicate char)
 * @param Rpos2 pointer to which the second starting position is stored (or -1 if no duplicate char)
 * @return the length of the longest repeating substring, or 0 if no character occurs twice
 */
int longestRepeatingSubstring(const char *A, int len, int *Rpos1, int *Rpos2) {
	int maxlen = 0; // longest repeating found this far
	int maxpos1 = -1;
	int maxpos2 = -1;

	int offset = 1; // difference of starting positions
	while (offset < len-1) {

		int pos1 = 0;   // start from beginning
		int pos2 = offset;
		int samelen = 0;    // how many same characters encountered
		int samestart1 = -1;    // start index of current streak of same charcters
		int samestart2 = -1;

		while (pos2 < len) {    // pos2 > pos1, iterate to the end
			if (A[pos1] == A[pos2]) {   // same character
				if (samestart1 == -1) { // start of new common sequence
					samestart1 = pos1;
					samestart2 = pos2;
				}
				samelen++;
				if (samelen > maxlen) { // new maximum found
                    maxpos1 = samestart1;
                    maxpos2 = samestart2;
					maxlen = samelen;
				}
			} else {    // different chacter, reset counters
				samelen = 0;
				samestart1 = -1;
				samestart2 = -1;
			}
			pos1++;
			pos2++;
		}
		offset++;
	}
	// store results and return
	*Rpos1 = maxpos1;
	*Rpos2 = maxpos2;
	return maxlen;
}


/**
 * Longest repeating substring of string A.
 * The substrings may overlap partially.
 * @param A input string
 * @param len  length of A
 * @param Rpos1 pointer to which the first starting position is stored (or -1 if no duplicate char)
 * @param Rpos2 pointer to which the second starting position is stored (or -1 if no duplicate char)
 * @return the length of the longest repeating substring, or 0 if no character occurs twice
 */
int longestRepeatingSubstring_mpi(const char *A, int len, int *Rpos1, int *Rpos2) {
	int maxlen = 0;
	int index1 = -1;
	int index2 = -1;

    #pragma omp parallel firstprivate(len) default(shared)
	  {
		int offset;
		int pmaxlen = 0;
		int pindex1 = -1;
		int pindex2 = -1;
		#pragma omp for schedule(static, 8)
		for (offset = 1; offset < len-1; offset++) {
			int pos1 = 0;
			int pos2 = offset;
			int samelen = 0;
			int samestart1 = -1;
			int samestart2 = -1;
			while (pos2 < len) {
				if (A[pos1] == A[pos2]) {
					if (samestart1 == -1) {
						samestart1 = pos1;
						samestart2 = pos2;
					}
					samelen++;
					if (samelen > pmaxlen) {
						pindex1 = samestart1;
						pindex2 = samestart2;
						pmaxlen = samelen;
					}
				} else {
					samelen = 0;
					samestart1 = -1;
					samestart2 = -1;
				}
				pos1++;
				pos2++;
			}
		}
		#pragma omp critical
		  {
			if (pmaxlen > maxlen) {
				maxlen = pmaxlen;
				*Rpos1 = pindex1;
				*Rpos2 = pindex2;
			}
		  }
	  }
	return maxlen;
}

int longestRepeatingSubstring2(const char *A, int len, int *Rpos1, int *Rpos2) {
	int offset, i, pos1, pos2;
	int maxlen = 0;
	int index1 = -1;
	int index2 = -1;

	for (pos1 = 0; pos1 < len-1; pos1++) {
		int samelen = 0;
		int samestart1 = -1;
		int samestart2 = -1;
		for (pos2 = pos1+1; pos2 < len; pos2++) {
			if (A[pos1] == A[pos2]) {
				if (samestart1 == -1) {
					samestart1 = pos1;
					samestart2 = pos2;
				}
				samelen++;
				if (samelen > maxlen) {
					index1 = samestart1;
					index2 = samestart2;
					maxlen = samelen;
				}
			} else {
				samelen = 0;
				samestart1 = -1;
				samestart2 = -1;
			}

		}

	}

	*Rpos1 = index1;
	*Rpos2 = index2;
	return maxlen;
}



double ltime()
{
    return omp_get_wtime();
}