说明：

最大不重复串Longest not repeat string，简称LNRS，即在一个字符串中寻找连续的，没有重复字符的最长子串

如"banana"，LNRS为"ban"

 

本文实现方法均是在别人的基础上，由本人实现，在此非常感谢大家的无私分享。

 

方法1：:暴力查找法，复杂度O(N^2)

方法2：由于暴力查找时会有重复查找，所以使用动态规划法提高效率

方法3：针对方法2进行空间优化

方法4：动态规划+hash法

 

 

// project1.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include
     
      #define LENGTH 1000//方法1：:暴力查找法，复杂度O(N^2)void LNRS_hash(char str[]){    //以*p开始的最大不重复子串    char *p=str;    int max=0,pos=0;    for(int i=0;*(p+i);i++){        int hash[256]={
   0};        int cur_max=0;        for(int j=i;*(p+j);j++){            if(hash[(unsigned int)*(p+j)]==0){                hash[(unsigned int)*(p+j)]++;                cur_max++;                }            else {                if(cur_max>max){                    max=cur_max;                    pos=i;                }                break;            }        }    }    printf("LNRS length:%d, begins at %d\n",max,pos);}//动态规划法void LNRS_dp(char str[]){    int len=strlen(str);    /*dp数组存的并不是LNRS，例如'abcdd'    * dp[4]=0,而不是dp[4]=4    * 对于dp[n]，只有一种情况>dp[n-1]    * 即str[n]添加到LNRS    */    int dp[LENGTH];    for(int i=0;i
      
       =last_beg;j--){            if(str[j]==str[i]){
   //出现重复                dp[i]=i-j;                last_beg=j+1;                break;            }            else if(j==last_beg)                 dp[i]=dp[i-1]+1;                    }        if(dp[i]>max){
   //LNRS加1            max=dp[i];            pos=i+1-max;        }    }    printf("LNRS length:%d, begins at %d\n",max,pos);}//动态规划法--改善空间，针对LNSR_dp的空间优化void LNRS_dp2(char str[]){    int len=strlen(str);    int dp=1;    int max=0,pos=-1,last_beg=0;    for(int i=1;i
       
        =last_beg;j--){            if(str[j]==str[i]){
   //出现重复                dp=i-j;                last_beg=j+1;                break;            }            else if(j==last_beg)                 dp++;                    }        if(dp>max){
   //LNRS加1            max=dp;            pos=i+1-max;        }    }    printf("LNRS length:%d, begins at %d\n",max,pos);}/* LNRS dp + hash 优化 */void LNRS_dp_hash_impro(char * arr){    int size=strlen(arr);    int visit[256];//记录某个字符最近出现的位置    for(int i=0;i<256;i++)        visit[i]=-1;    int maxlen = 0,maxindex = 0;    visit[arr[0]] = 0;    int curlen = 1;    int last_start = 0;    for(int i = 1; i < size; ++i){        if(visit[arr[i]] == -1){
   //未曾出现            ++curlen;            visit[arr[i]] = i; /* 记录字符下标 */        }        else{
   //已经出现过            //如果arr[i]上次出现的位置在last_start之后            //例如abcdc，i=4时，c出现的位置在last_start（0）之后            //则肯定无效            if(last_start <= visit[arr[i]]){                curlen = i - visit[arr[i]];                last_start = visit[arr[i]]+1;                visit[arr[i]] = i; /* 更新最近出现位置 */            }            else{                ++curlen;                visit[arr[i]] = i; /* 更新最近出现位置 */            }        }        if(curlen > maxlen){            maxlen = curlen;            maxindex = i + 1 - maxlen;        }    }    printf("LNRS length:%d, begins at %d\n",maxlen,maxindex);}int _tmain(int argc, _TCHAR* argv[]){    char str1[LENGTH]="banana";    char str2[LENGTH]="aabbccdjlhiuerkjhefabcdeabcdabcaba";    char str3[LENGTH]="12341343245656123";    char str4[LENGTH]="abcdda";    char str5[LENGTH]="banaa";    char str6[LENGTH]="2456561";        LNRS_hash(str1);LNRS_hash(str2);LNRS_hash(str3);    LNRS_dp(str1);LNRS_dp(str2);LNRS_dp(str3);    LNRS_dp2(str1);LNRS_dp2(str2);LNRS_dp2(str3);    LNRS_dp_hash_impro(str1);LNRS_dp_hash_impro(str2);LNRS_dp_hash_impro(str3);    return 0;}