动态规划经典之求字符串的最长不重复子串

题目要求：找到一个字符串中的一个连续子串，这个子串内不能有任何两个字符是相同的，并且这个子串是符合要求的最长的。

例如：abcdeab，这个字符串有很多不重复子串，比如：abcde, bcdea, cdeab都是不重复子串，而且都是最长的。

这个是一个经典的笔试题，百度也曾经出过。我这里只输出一个最长的!!!

 

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

void find_max_no_repeat(char* str, int* index, int* max)
{
  int i;
  int current_len = 0;
  int current_start = 0;
  int A[26];
  
  for(i=0;i<26;i++)
    A[i]=-1;
   
 
  for(i=0;i<N;i++)
   {
     if(A[str[i]-'a']!=-1)
      {
       if(A[str[i]-'a']+1>current_start)
          current_start = A[str[i]-'a']+1;

       current_len = i-current_start+1;
       A[str[i]-'a'] = i;
     }
     else
      {
       A[str[i]-'a'] = i;
       current_len++;
      }
      
      
       if(current_len>*max)
         {
          *max = current_len;
          *index = current_start;
         }
      
   }
    
}

int main(int argc, char *argv[])
{
  int i;
  int index = 0;
  int max = 0;
  char str[N+1];
  
  srand((unsigned int)time(NULL));
  
  for(i=0;i<N;i++)
   str[i] = 'a'+rand()%N;
  str[N] = '\0';
  
  find_max_no_repeat(str, &index, &max);
  printf("max no repeat in %s is:\n", str);
  for(i=0;i<max;i++)
     printf("%c",str[i+index]);
  
  printf("\n");
  system("PAUSE");    
  return 0;
}


 

 

if(A[str[i]-'a']!=-1)
      {
       if(A[str[i]-'a']+1>current_start)
          current_start = A[str[i]-'a']+1;

       current_len = i-current_start+1;
       A[str[i]-'a'] = i;      
     }
     else
      {
       A[str[i]-'a'] = i;                   
       current_len++;
      }

这个事程序主体,我举个例子吧,输入abcdab

a的时候,由于A['a'-'a']==-1于是A[0]=0,current_len=1;

b同上A[1]=1,current_len=2;

c同上A[2]=2,current_len=3;

d同上A[3]=3,current_len=4;

a的时候发现A[0]!=-1 走

       if(A[str[i]-'a']+1>current_start)
          current_start = A[str[i]-'a']+1;//current_start=1

       current_len = i-current_start+1; current_len = 4
       A[str[i]-'a'] = i; //A[0]=4

b的时候发现A[1]!=-1 走

       if(A[str[i]-'a']+1>current_start)
          current_start = A[str[i]-'a']+1;//current_start=2

       current_len = i-current_start+1; current_len = 4
       A[str[i]-'a'] = i; //A[1]=5

大致就是这么个流程,自己分析下应该问题不大