精华内容
下载资源
问答
  • 最长重复子串问题

    千次阅读 2013-07-24 17:29:55
    最长重复子串是指在一个字符串中找出最长的出现两次或两次以上的子串,例如abcdeabbcde,则bcde则是最长的重复子串。 最直观的解法是穷举所有的子串,和原串进行对比,从而选出最长的重复子串。 #include #...

    最长重复子串是指在一个字符串中找出最长的出现两次或两次以上的子串,例如abcdeabbcde,则bcde则是最长的重复子串。

    最直观的解法是穷举所有的子串,和原串进行对比,从而选出最长的重复子串。

    #include <stdio.h>
    #include <string.h>
    
    
    int commonLen(const char *str1, const char *str2){
            int len = 0;
            if(str1 == NULL || str2 == NULL){
                    return 0;
            }
            while(*str1 && * str2 && *str1 == *str2){
                    str1++;
                    str2++;
                    len++;
            }
            return len;
    }
    
    int LRS(const char *str){
            if(str == NULL){
                    return 0;
            }
            int i, j;
            int maxlen = 0, curlen = 0, maxindex = 0;
            int len = strlen(str);
            for(i = 0; i < len; i++){
                    for(j = i + 1; j < len; j++){
                            curlen = commonLen(str + i, str + j);
                            if(curlen > maxlen){
                                    maxlen = curlen;
                                    maxindex = i;
                            }
                    }
            }
            for(i = 0; i < maxlen; i++){
                    printf("%c", *(str + maxindex + i));
            }
            return maxlen;
    }
    
    int main(){
            char *str = "abcdeabbcde";
            int len = LRS(str);
            printf("Max LRS = %d\n", len);
    }
    这种算法的效率是O(N^3),效率不高,使用过KMP算法的同学会联想到这其实就是在求next数组的最大值问题,例如“abcdabcde”,它的next数组为:

    -1      0       0       0       0       1       2       3       4       0

    各个子串的next数组的最大值就是最长重复子串的长度。

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    int maxNext(const char *s, int _next[]){
            _next[0] = -1;
            int i = 0;
            int j = -1;
            int max = 0;
            int len = strlen(s);
            while(i < len){
                    if(j == -1 || s[i] == s[j]){
                            i++;
                            j++;
                            _next[i] = j;
                            if(j > max){
                                    max = j;
                            }
                    }else{
                            j = _next[j];
                    }
            }
            return max;
    }
    
    int LRS_KMP(const char *str){
            int len = strlen(str);
            int index = 0;
            int max = 0;
            int maxindex = 0;
            int *_next = (int *)malloc(len * sizeof(int));
            int i;
            for(i = 0; i < len - 1; i++){
                    int curmax = maxNext(str + i, _next);
                    if(curmax > max){
                            max = curmax;
                            maxindex = i;
                    }
            }
            for(i = 0; i < max; i++){
                    printf("%c", *(str + maxindex + i));
            }
            return max;
    }
    
    int main(){
            char *str = "abaabaaabaaaab";
            int len = LRS_KMP(str);
            printf("Max LRS = %d\n", len);
    }





    展开全文
  • JAVA算法:最长重复子串问题(JAVA解题) Given a string str, find the longest repeating non-overlapping substring in it. In other words find 2 identical substrings of maximum length which do not ...

    JAVA算法:最长重复子串问题(JAVA解题)

    Given a string str, find the longest repeating non-overlapping substring in it. In other words find 2 identical substrings of maximum length which do not overlap. If there exists more than one such substring return any of them.

    Examples:

    Input : str = "geeksforgeeks"
    Output : geeks

    Input : str = "aab"
    Output : a

    Input : str = "aabaabaaba"
    Output : aaba

    Input : str = "aaaaaaaaaaa"
    Output : aaaaa

    Input : str = "banana"
    Output : an 
             or na


    算法设计

    package com.bean.algorithm.basic;
    
    public class LongestRepeatingSubstring {
    	// Returns the longest repeating non-overlapping
    	// substring in str
    	static String longestRepeatedSubstring(String str) {
    		int n = str.length();
    		int LCSRe[][] = new int[n + 1][n + 1];
    
    		String res = ""; // To store result
    		int res_length = 0; // To store length of result
    
    		// building table in bottom-up manner
    		int i, index = 0;
    		for (i = 1; i <= n; i++) {
    			for (int j = i + 1; j <= n; j++) {
    				// (j-i) > LCSRe[i-1][j-1] to remove
    				// overlapping
    				if (str.charAt(i - 1) == str.charAt(j - 1) && LCSRe[i - 1][j - 1] < (j - i)) {
    					LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1;
    
    					// updating maximum length of the
    					// substring and updating the finishing
    					// index of the suffix
    					if (LCSRe[i][j] > res_length) {
    						res_length = LCSRe[i][j];
    						index = Math.max(i, index);
    					}
    				} else {
    					LCSRe[i][j] = 0;
    				}
    			}
    		}
    
    		// If we have non-empty result, then insert all
    		// characters from first character to last
    		// character of String
    		if (res_length > 0) {
    			for (i = index - res_length + 1; i <= index; i++) {
    				res += str.charAt(i - 1);
    			}
    		}
    
    		return res;
    	}
    
    	// Driver program to test the above function
    	public static void main(String[] args) {
    		String str = "aabaabaaba";
    		System.out.println(longestRepeatedSubstring(str));
    	}
    
    }
    

    程序运行结果:

     aaba

     

     

    展开全文
  • 问题描述:给定一个字符串,求最长重复子串,这两个子串可以重叠。 ...求可重叠最长重复子串等价于求两个后缀的最长公共前缀的最大值,而形成最长公共前缀的子串一定是排名相邻的,所以问题解决。

    问题描述:给定一个字符串,求最长重复子串,这两个子串可以重叠。

     

    其实问题可以转化为height数组的最大值。至于为什么是这样,我可以这样解释:

    求可重叠最长重复子串等价于求两个后缀的最长公共前缀的最大值,而形成最长公共前缀的子串一定是排名相邻的,所以问题解决。

      

    展开全文
  • 最长不可重叠重复子串,也可以利用height[i]height[i]height[i]。 二分枚举答案KKK 当height[i]≥Kheight[i] \ge Kheight[i]≥K可能存在解,然后判断min(sa[i],sa[i−1]),max(sa[i],sa[i−1])min(sa[i], sa[i-1]...

    题目链接

    思路

    求不可重叠最长重复子串,也可以利用height[i]height[i]

    • 二分枚举答案KK
    • height[i]Kheight[i] \ge K可能存在解,然后判断min(sa[i],sa[i1])max(sa[i],sa[i1])min(sa[i], sa[i-1]),max(sa[i], sa[i-1])的关系,看能否构造成不重叠的公共前缀
    • height[i]height[i]数值相同的分成一组,取小组中的最值计算
    #include <bits/stdc++.h>
    #define LL long long
    #define P pair<int, int>
    #define lowbit(x) (x & -x)
    #define mem(a, b) memset(a, b, sizeof(a))
    #define mid ((l + r) >> 1)
    #define lc rt<<1
    #define rc rt<<1|1
    #define endl '\n'
    const int maxn = 1e5 + 5;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    using namespace std;
    int cntA[maxn], cntB[maxn], A[maxn], B[maxn];
    int Sa[maxn], tsa[maxn], height[maxn], Rank[maxn];
    int s[maxn];
    int n;
    void suffixArray () {
    	for (int i = 0; i < 1000; ++i) cntA[i] = 0;
    	for (int i = 1; i <= n; ++i) cntA[s[i]]++;
    	for (int i = 1; i < 1000; ++i) cntA[i] += cntA[i-1];
    	for (int i = n; i >= 1; --i) Sa[ cntA[s[i]]-- ] = i;
    	Rank[ Sa[1] ] = 1;
    	for (int i = 2; i <= n; ++i) {
    		Rank[Sa[i]] = Rank[Sa[i-1]];
    		if (s[Sa[i]] != s[Sa[i-1]]) Rank[Sa[i]]++;
    	}
    	for (int l = 1; Rank[Sa[n]] < n; l <<= 1) {
    		for (int i = 0; i <= n; ++i) cntA[i] = 0;
    		for (int i = 0; i <= n; ++i) cntB[i] = 0;
    		for (int i = 1; i <= n; ++i) {
    			cntA[ A[i] = Rank[i] ]++;
    			cntB[ B[i] = (i + l <= n) ? Rank[i+l] : 0]++;
    		}
    		for (int i = 1; i <= n; ++i) cntB[i] += cntB[i-1];
    		for (int i = n; i >= 1; --i) tsa[ cntB[B[i]]-- ] = i;
    		for (int i = 1; i <= n; ++i) cntA[i] += cntA[i-1];
    		for (int i = n; i >= 1; --i) Sa[ cntA[A[tsa[i]]]-- ] = tsa[i];
    		Rank[ Sa[1] ] = 1;
    		for (int i = 2; i <= n; ++i) {
    			Rank[Sa[i]] = Rank[Sa[i-1]];
    			if (A[Sa[i]] != A[Sa[i-1]] || B[Sa[i]] != B[Sa[i-1]]) Rank[Sa[i]]++;
    		}
    	}
    	for (int i = 1, j = 0; i <= n; ++i) {
    		if (j) --j;
    		int tmp = Sa[Rank[i] - 1];
    		while (i + j <= n && tmp + j <= n && s[i+j] == s[tmp+j]) ++j;
    		height[Rank[i]] = j;
    	}
    }
    int check(int x) {
    	int minsa = 1e9, maxsa = -1e9;
    	for (int i = 1; i <= n; ++i) {
    		if (height[i] >= x) {
    			minsa = min(minsa, Sa[i]);
    			maxsa = max(maxsa, Sa[i]);
    			if (maxsa - minsa >= x) return 1;
    		}else {
    			minsa = Sa[i];
    			maxsa = Sa[i];
    		}
    	}
    	return 0;
    }
    
    int main () {
    	ios::sync_with_stdio(0);
        cin.tie(0), cout.tie(0);
    	cin >> n;
    	for (int i = 1; i <= n; ++i) {
    		cin >> s[i];
    	}
    	suffixArray();
    	int l = 1, r = n;
    	while (l <= r) {
    		if (check(mid)) l = mid + 1;
    		else r = mid - 1;
    	}	
    	cout << r << endl;
    	return 0;
    }
    
    展开全文
  • /******此算法在于解决判断第一个最长重复子串的位置,并灵活使用next函数值解决问题。 核心在于next函数值反应的是串中重复的字符个数,故通过next函数将字符串一个个分解开来, 如将banana 分解为“banana”,...
  • 最长重复子串和最长不重复子串求解 本文内容框架: §1 最长重复子串 基本方法、KMP算法求解、后缀数组求解 §2 最长不重复子串 基本方法、动态规划、动态规划+Hash §3 小结   §...
  • 经典问题,记录一下这道题解法问题描述给定一个字符串,找到最长子串的长度,要求子串不含不重复字符。样例给定"pwkpwo"的答案是是4("kpwo")。给定"bbbbb"的答案是1("b")。解法1.双指针-滑动窗口i:表示窗口左端点j...
  • LeetCode(3)最长重复子串的实现
  • 给定一个字符串,找到最长子串,要求该子串中没有重复的字符。 例如: 字符串abcabcbb的不含重复字符的 最长 子串为abc,长度为 3。 而bbbbbb的不含重复字符的 最长 子串为b,长度为 1。 输入格式 输入...
  • 求最长回文子串最长重复子串。长沙雅礼中学何林【介绍】问题的提出:问题1最长回文子串顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。输入...
  • 算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识...今天和大家聊的问题叫做最长重复子串,这道题很有意思,我们先来看题面:Given a string, find the length of the longest substring without r...
  • 给定一个字符串str,求该字符串中的最长重复子串的长度。 如“abcd”的最长重复子串是“abcd”,长度为4;“abcb”的最长重复子串是“abc”,长度为3。 题目思路: 遍历字符串,表示出以每个字符串元素str...
  • 动态规划法 ...为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。 【问题】 求两字符序列的最长公共字
  • 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例2: 输入: "bbbbb" 输出: 1 解释: 因为无...
  • 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 利用滑动窗口 时间复杂度:o(n^2) 空间复杂度...
  • 提示:该系列整理子串问题。 文章目录系列文章目录一、找到字符串的最长重复字符子串1.滑动窗口法:2.双指针+回头遍历 一、找到字符串的最长重复字符子串 给定一个数组 arr,返回 arr 的最长重复的字串的...
  • 原题目给定一个字符串,找出不含有重复字符的最长子串的长度。示例:给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是给定 "bbbbb" ,最长子串就是 "b" ,长度是1。给定 "pwwkew" ,最长子串是 ...
  • #include #include using namespace std; void GetNext(char s[], int next[], int length); int MaxRepSubString(char s[],int &l,int length); int main () { char v[1000]; char c;...}
  • 字符串应用--密码截获 求最长回文子串
  • 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 //思路:用双指针,滑动窗,遇到重复的,左指针就到重复的下标处,用max保存当前最大长度 class Solution { public int ...
  • 本文实例讲述了Python实现针对给定字符串寻找最长重复子串的方法。分享给大家供大家参考,具体如下:问题:给定一个字符串,寻找其中最长的重复子序列,如果字符串是单个字符组成的话如“aaaaaaaaaaaaa”那么满足...
  • 这里把最大子序列和放在第一个位置,它并不是字符串相关的问题,事实上它的目的是要找出由数组成的一维数组中和最大的连续子序列。比如[0,-2,3,5,-1,2]应返回9,[-9,-2,-3,-5,-3]应返回-2。 1、动态...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 901
精华内容 360
关键字:

最长重复子串问题