leetcode/1044-longest-duplicate-substring.go

package main

import "sync"

func LongestDupSubstringBruteforce(s string) string {
	strLen := len(s)
	if strLen < 2 {
		return ""
	}

	res := ""
	for ln := 1; ln < strLen; ln++ {
		for i := 0; i <= strLen-ln; i++ {
			word1 := s[i : i+ln]
			count := 0
			for j := 0; j <= strLen-ln; j++ {
				word2 := s[j : j+ln]
				if word1 == word2 {
					count++
					if count > 1 {
						res = word1
						break
					}
				}
			}
		}
	}

	return res
}

func LongestDupSubstringReversedBruteforce(s string) string {
	strLen := len(s)
	if strLen < 2 {
		return ""
	}

	for ln := strLen - 1; ln >= 1; ln-- {
		for i := strLen - ln; i >= 0; i-- {
			word1 := s[i : i+ln]
			count := 0
			for j := strLen - ln; j >= 0; j-- {
				word2 := s[j : j+ln]
				if word1 == word2 {
					count++
					if count > 1 {
						return word1
					}
				}
			}
		}
	}

	return ""
}

func LongestDupSubstringSmartforce(s string) string {
	strLen := len(s)
	if strLen < 2 {
		return ""
	}

	indicesCurrent := []int{}
	indicesNext := []int{}

	res := ""
	for i := 0; i < strLen-len(res); i++ {

		for j := 0; j < strLen; j++ {
			indicesCurrent = append(indicesCurrent, j)
		}

		for ln := 1; ln <= strLen-i; ln++ {
			word1 := s[i : i+ln]

			for _, index := range indicesCurrent {
				if index+ln > strLen {
					continue
				}
				word2 := s[index : index+ln]
				if (word1 == word2) && (index != i) {

					if len(res) < len(word1) {
						res = word1
					}
					indicesNext = append(indicesNext, index)
				}
			}

			indicesCurrent = indicesNext
			indicesNext = []int{}
		}
	}

	return res
}

func LongestDupSubstringSmartforceMark2(s string) string {
	strLen := len(s)
	if strLen < 2 {
		return ""
	}

	indicesNext := []int{}
	indicesAll := []int{}

	for j := 0; j < strLen; j++ {
		indicesAll = append(indicesAll, j)
	}

	res := ""
	for i := 0; i < strLen-len(res); i++ {
		indicesCurrent := indicesAll

		for ln := 1; ln <= strLen-i; ln++ {
			word1 := s[i : i+ln]

			for _, index := range indicesCurrent {
				if index+ln > strLen {
					continue
				}

				word2 := s[index : index+ln]
				if (index != i) && (word1 == word2) {
					if len(res) < len(word1) {
						res = word1
					}
					indicesNext = append(indicesNext, index)
				}
			}

			indicesCurrent = indicesNext
			indicesNext = []int{}
		}
	}

	return res
}

func LongestDupSubstringBruteforceReversedMark2(s string) string {
	strLen := len(s)
	if strLen < 2 {
		return ""
	}

	res := ""
	for ln := strLen - 1; ln > 0; ln-- {

		if ln < len(res) {
			break
		}

		for i := 0; i < strLen-ln; i++ {
			word1 := s[i : i+ln]
			for j := i + 1; j+ln <= strLen; j++ {
				word2 := s[j : j+ln]
				if word1 == word2 {
					if len(res) < len(word1) {
						res = word1
					}
					break
				}
			}
		}
	}
	return res
}

func LongestDupSubstringSmartforceMark3(s string) string {
	strLen := len(s)
	if strLen < 2 {
		return ""
	}

	indicesNext := []int{}
	indicesAll := []int{}

	for j := 0; j < strLen; j++ {
		indicesAll = append(indicesAll, j)
	}

	res := ""
	for i := 0; i < strLen-len(res); i++ {
		indicesCurrent := indicesAll[i+1:]

		for ln := 1; ln <= strLen-i; ln++ {

			word1 := s[i : i+ln]

			for _, index := range indicesCurrent {
				if index+ln > strLen {
					continue
				}

				if s[i+ln-1] == s[index+ln-1] {
					if len(res) < len(word1) {
						res = word1
					}
					indicesNext = append(indicesNext, index)
				}
			}

			indicesCurrent = indicesNext
			indicesNext = []int{}
		}
	}

	return res
}

func LongestDupSubstringSmartforceMark3Goroutine(s string, from int, to int) string {
	strLen := len(s)
	if strLen < 2 {
		return ""
	}

	indicesNext := make([]int, 0, len(s))
	indicesAll := make([]int, 0, len(s))
	indicesEmpty := make([]int, 0, len(s))

	for j := 0; j < strLen; j++ {
		indicesAll = append(indicesAll, j)
	}

	res := ""
	for i := from; (i < to) && (i < strLen-len(res)); i++ {
		indicesCurrent := indicesAll[i+1:]

		for ln := 1; ln <= strLen-i; ln++ {

			word1 := s[i : i+ln]

			for _, index := range indicesCurrent {
				if index+ln > strLen {
					continue
				}

				if s[i+ln-1] == s[index+ln-1] {
					if len(res) < len(word1) {
						res = word1
					}
					indicesNext = append(indicesNext, index)
				}
			}

			indicesCurrent = indicesNext
			indicesNext = indicesEmpty
		}
	}

	return res
}

func LongestDupSubstringGoroutines(s string) string {
	threads := 24
	results := make([]string, threads)
	interval := len(s) / threads

	if interval < (800 / threads) {
		return LongestDupSubstringSmartforceMark3Goroutine(s, 0, len(s))
	}

	wg := new(sync.WaitGroup)
	wg.Add(threads)

	for i := 0; i < threads-1; i++ {
		go func(input int) {
			results[input] = LongestDupSubstringSmartforceMark3Goroutine(s, input*interval, input*interval+interval)
			wg.Done()
		}(i)
	}

	go func(input int) {
		results[input] = LongestDupSubstringSmartforceMark3Goroutine(s, input*interval, len(s))
		wg.Done()
	}(threads - 1)

	wg.Wait()

	resLen := -1
	res := ""

	for _, w := range results {
		if len(w) > resLen {
			resLen = len(w)
			res = w
		}
	}

	return res
}

func DupSubstringLengthN(s string, n int) string {
	StringMap := map[string]interface{}{}

	for begin := 0; begin <= len(s)-n; begin++ {
		end := begin + n
		str := s[begin:end]

		_, ok := StringMap[str]
		if ok {
			return str
		}

		StringMap[str] = nil
	}

	return ""
}

func LongestDupSubstringBinarySearchAndMap(s string) string {
	maxLen := 0
	dups := map[int]string{}
	dups[0] = ""

	left := 0
	right := len(s)
	mid := 0

	for left < right {
		mid = (left + right) / 2
		res := DupSubstringLengthN(s, mid)

		if len(res) > 0 {
			dups[mid] = res
			left = mid + 1
			if mid > maxLen {
				maxLen = mid
			}
		} else {
			right = mid
		}
	}

	return dups[maxLen]
}

func LongestDupSubstring(s string) string {
	return LongestDupSubstringBinarySearchAndMap(s)
}