/* maxsubstring.c 输出最长不重复子串*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 50
typedef struct LNODE{
    struct LNODE *nextp;
    char* sub;
}LNode;
LNode *rootp = NULL;

void add_node(char *s);
void empty_node(void);
void print_node(void);
char *str_dup(char *s);
void create_node(char *s);

int main(void)
{
    char queue[MAXSIZE];
    char sub[MAXSIZE];
    int front, rear, maxlen;
    int i, j, ch, flag = 1;
   
    queue[0] = getchar();         /* 读取第一个字符，不读取程序没办进行比较 */
    front = rear = maxlen = 0;      /* front，rear分别为队列第一，最后一个字符的下标 */
    while((ch = getchar()) != '\n' && maxlen < MAXSIZE){
        for(i = 0; i < rear + 1; i++)    /* 长度为rear+1的数组内查找相同的字符 */
            if(queue[i] == ch){           /* 如果找到了，则进行如下计算 */
                front = i + 1;
                for(j = 0; j < (rear - i); j++)  /* 从j开始，把rear-i个字符移动到队首 */
                    queue[j] = queue[front++];
                rear -= i;                        /* 重置队列尾部 */
                queue[rear] = ch;                 /* 把新读取的字符添加在尾部 */
                flag = 0;
                break;
            }
        if(flag)    /* 如果数组内没有找到相同的字符，则把新字符添加在队列尾部 */
            queue[++rear] = ch;
        else
            flag = 1;
        if(maxlen < rear + 1){   /* 保存数组最长记录*/
            maxlen = rear + 1;
            for(i = 0; i < maxlen; i++)   /* 记录下最长的子字符串 */
                sub[i] = queue[i];
            sub[i] = '\0';
            empty_node();
            create_node(str_dup(sub));
        }else if(maxlen == rear + 1){
            for(i = 0; i < maxlen; i++)   /* 记录下相同长度的子字符串 */
                sub[i] = queue[i];
            sub[i] = '\0';
            printf("%s", sub);
            add_node(str_dup(sub));
        }
        front = 0;
//        for(i = 0; i <= rear; i++)            /* 此三行为调试用代码 */
//            printf("%c", queue[i]);
//        printf("\trear = %d\n",rear);
    }
    printf("最长的不重复字符串为：");
//    for(i = 0; i <maxlen; i++)
//        printf("%c", sub[i]);
    print_node();
    printf("共有%d个字符\n", maxlen);
    empty_node();
    return 0;
}

void add_node(char *s)   // 添加新节点
{
    LNode *np, *newp, *previous;
   
    if((newp = (LNode *)malloc(sizeof(LNode))) == NULL){
        printf("申请内存失败，无法添加新节点\n");
        exit(1);
    }
    newp->sub = s;
    newp->nextp = NULL;
    np = rootp;
    while(np != NULL){
        previous = np;
        np = np->nextp;
    }
    previous->nextp = newp;
}

void empty_node(void) // 清空链表，释放内存
{
    LNode *np, *temp;
   
    for(np = rootp; np != NULL; free(temp) ){  
        temp = np;
        free(temp->sub);
        np = np->nextp;
    }
    rootp = NULL;
}

void print_node(void)   //打印链表
{
    LNode *np;
   
    for(np = rootp; np != NULL; np = np->nextp )  
        printf("\"%s\",",np->sub);
}

void create_node(char *s)  // 创建新的链表
{
    if(rootp != NULL){
        printf("链表未清空！\n");
        exit(2);
    }
    if((rootp = (LNode *)malloc(sizeof(LNode))) == NULL){
        printf("申请内存失败，无法添加新节点\n");
        exit(1);
    }
    rootp->sub = s;
    rootp->nextp = NULL;
}

char *str_dup(char *s)  /* 复印S到某个位置 */
{
    char *p;
   
    p = (char *)malloc(strlen(s) + 1);
    if(p != NULL)
        strcpy(p, s);
    return p;
}

// 用链表实现保存多个相同长度字符串，感觉整得越来越复杂了，不过通过这个例子学会了如何操控队列和简单链表。

[此贴子已经被作者于2016-12-11 11:05编辑过]

不知道是我理解错了，还是本来就很复杂！又是双指针、又是动态内存的，不好懂耶。我这笨笨的脑袋只想的出下述代码，好像可以输出所有最长子串，期待大神们测试并指出错误！

#include<stdio.h>
void maxlen(char* s,int& start,int& len)
{//查找字符串中最长不重复子串，返回子串起点在start，子串长度在len
    int i,j,k,l;
    for(l=0;s[l];l++);  //首先获取原始字符串长度在l里
    if(start<0||start>=l)start=0;  //起始位置未初始化的处理
    for(i=start,len=0;i+len<l;)
    {
        for(j=i+1;s[j];j++)
        {
            for(k=j-1;k>i&&s[j]!=s[k];k--); //倒查是否有重复
            if(s[j]==s[k])break;
        }
        if(j-i>len)
        {
            start=i;
            len=j-i;  //记录当前最大子串的起点位置和子串长度
        }
        i=j;  //原始起点位置不逐步自加，而是等于下一个重复字符起点位置可提高效率，同理循环条件是i+len<l也是提高执行效率
    }
}

void main()
{
    char str[80];
    int i,j,s,l,m,e;
    gets(str);
    for(e=0;str[e];e++);
    for(i=0,m=0;i+m<=e;i++)
    {//输出所有最长子串"abcdab: abcd bcda cdab"
        s=i;
        maxlen(str,s,l);
        if(m==0)
        {
            m=l;
            i=s;
        }
        if(l>=m)
        {
            for(j=0;j<l;j++)printf("%c",str[j+s]); //根据最长子串起点和长度输出该子串所有字符
            printf("\n");
        }
    }
}

可以可以不过感觉上要取出所有不重复的子串要比取只取其中一个最值的遍历次数要多很多，倒不如第一次先求最大长度，不保留子串，第二次再根据最值保留字符串。保留字符串用一个动态数组（可以用realloc来扩大空间）处理，每次输出长度为max的值行了。

看来并没有认真看我的代码！自认这个代码无论是找单个最长的还是找所有最长的应该是效率比较高的一个。

如果输入：121234121234，那么程序就是错的。

为什么你们的C语言编译器跟我的大不一样？void maxlen(char* s,int& start,int& len)这样传递参数，我的必须是void maxlen(char* s,int start,int len)，主函数main()默认是int类型而不是void。另外，你的程序在我的电脑上无法正确执行?这是可移植性问题，还是编译问题？

感谢指正！
代码未能正确修正最长字符起始比较位置，导致最后一个长子串多输出几次了，修正如下：
    for(i=0,m=0;i+m<=e;i++)
    {//输出所有最长子串"abcdab: abcd bcda cdab"
        s=i;
        maxlen(str,s,l);
        if(m==0)m=l;
        if(s>i)i=s;
        if(l>=m)
        {
            for(j=0;j<l;j++)printf("%c",str[j+s]); //根据最长子串起点和长度输出该子串所有字符
            printf("\n");
        }
    }

[此贴子已经被作者于2016-12-11 18:47编辑过]

vs2010,函数参数里&是变量引用，真正意义上的传址，相当于在墙上打个洞，摆弄隔壁房间的东西。

我笑了 其实我不但测试过你的代码，而且还改过你的代码。恕我编译器资源稀少，我手头暂时只有vc6,（迟点也许会更新）就是说函数加个地址vc是不支持的，改了加指针，然后在循环处设置了输出点测试了比较次数，效果我就不说了，自己知。单个字符输出来说可以说是我原版提供的最为理想，其次是队列（r版主的要改改我的编译器才能测试，这个先保留）。当然，如果我真的要改，第一次先求最大长度，然后第二次再输出所有最长子串，顶多效率降为原来的一半而已。不过你做求mathisfun那题还真不错，感觉那题型和你用的方法和这题有点共同之处。

[此贴子已经被作者于2016-12-11 19:13编辑过]

感谢你做了测试！我那代码vc6是能够编译的，我今天一天待在实验室，那里装的就是vc6(还有codeblocks，调试不习惯），现回宿舍了，笔记本上装的是vs2010，一样编译成功。
能不能将那个测试执行效率的代码发给我？我想亲自测试。

又发现了一个bug，