Longest Duplicate Substring

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.
Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is

Example 1:

Input: s = "banana"
Output: "ana"

Approach

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class LongestDuplicateSubstring {
    public static void main(String[] args) {
        String s = "banana";
        System.out.println(longestDupSubstring(s));
    }

    static int power[];

    static String ret;
    static int prime = 10000007;

//rabincarp function for string matching
    static String rabincarp(String s, int k) {
        if (k == 0)
            return "";
        long hash = 0;
        HashMap<Long, List<Integer>> set = new HashMap<>();
        
        for (int i = k - 1; i >= 0; i--) {
            hash = (hash % prime + (power[k - 1 - i] * (s.charAt(i) - 'a' + 1))
                         % prime) % prime;
        }
        int i = 0, j = k - 1;
        List<Integer> l = new ArrayList<Integer>();
        l.add(1);
        l.add(0);
        set.put(hash, l);

        while (j < s.length()) {
            hash = (hash % prime - ((power[k - 1] * (s.charAt(i) - 'a' + 1))
                         % prime) + prime) % prime;
            hash = (hash % prime * 26 % prime) % prime;
            i++;
            j++;
            if (j < s.length()) {
                hash = (hash % prime + ((power[0] * (s.charAt(j) - 'a' + 1))
                             % prime)) % prime;
                if (set.containsKey(hash)) {
                    for (Integer ind : set.get(hash)) {
                        if (s.substring(ind, ind + k).equals(s.substring(i, i + k))) {
                            return s.substring(ind, ind + k);
                        }
                    }
                    List<Integer> l1 = new ArrayList<Integer>();
                    l1.add(i);
                    set.put(hash, l1);
                } else {
                    List<Integer> l1 = new ArrayList<Integer>();
                    l1.add(1);
                    l1.add(i);
                    set.put(hash, l1);
                }
            }
        }
        return "";
    }

    static String longestDupSubstring(String S) {
        int n = S.length();
        power = new int[n + 1];
        power[0] = 1;
        // rolling function base value
        int a = 26;
        for (int i = 1; i <= n; i++) {
            power[i] = (a * power[i - 1]) % prime;
        }
        int low = 0, high = n;
        String ans = "";
        // Binary Search
        while (low <= high) {
            int mid = low + (high - low) / 2;
            String x = rabincarp(S, mid);
            if (x.length() > 0) {
                if (x.length() > ans.length())
                    ans = x;
                low = mid + 1;
            } else
                high = mid - 1;
        }
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


vector<int> power;
string ret;
int prime=10000007;

//rabincarp funstion for string matching
string rabincarp(string &s,int &k)
{
        if(k==0)
              return "";
        long long int hash=0;
        unordered_map<int,vector<int> > mp;
        for(int i=k-1;i>=0;i--){
            hash=(hash%prime+(power[k-1-i]*(s[i]-'a'+1))%prime)%prime;
        }
        int i=0,j=k-1;
        mp[hash]=vector<int>(1,0);
        bool flag=0;
        while(j<s.size()){
            hash=(hash%prime-((power[k-1]*(s[i]-'a'+1))%prime)+prime)%prime;
            hash=(hash%prime*26%prime)%prime;
            i++;
            j++;
            if(j<s.size()){
                hash=(hash%prime+((power[0]*(s[j]-'a'+1))%prime))%prime;
                if(mp.find(hash)!=mp.end()){
                    for(auto ind:mp[hash]){
                        if (strcmp((s.substr(ind,k)).data(), s.substr(i, k).data()) == 0) {
                        return s.substr(ind,k);
                    }
                    }
                    mp[hash].push_back(i);
                }
                else{
                    mp[hash]=vector<int>(1,i);
                }
            }
        }
        return "";
}

string longestDupSubstring(string S) 
{
        int n=S.size();
        power.resize(n+1);
        power[0]=1;
        for(int i=1;i<=n;i++){
            power[i]=(26*power[i-1])%prime;
        }
        int low=0,high=n;
        string ans="";
        while(low<=high){
            int mid=low+(high-low)/2;
            string x=rabincarp(S,mid);
            if(x.size()>0)
            {
                if(x.size()>ans.size())
                    ans=x;
               low=mid+1;
            }
            else
                high=mid-1;
        }
        return ans;
}
int main()
{
    string s = "banana";
    cout<<longestDupSubstring(s);
    return 0;
}