字符串操作考点（经gcc调试）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处:snowboy.blog.chinaunix.net

雪夜流星

------------------------------------------

1.在字符串中查找最长重复子串：

   写一个函数，找出一个字符串中最长的重复子串。“t1t1”结果就是t1."cabcabca"结果就是cab或者abc或者bca。

说明：

假设str中有长度为m的连续子串，则字符串移动m个位置后，与原串
 s0 s1 s2 s3 ... sm-1 sm sm+1 sm+2 ..... sn
                            s0   s1  s2 .............sn

一定有连续m个位置的字符是相等的；如果有多个解，只返回第一个；

实现代码如下：

#include <stdio.h>
#include <stdlib.h>
#define BUF_MAX 1000

int index1; //子串起始位置（数组中的索引）
int len;//子串长度
void str_search(const char *str, char *sub)
{
     int i=0;
    int strlen = 0;

    /*计算源字符串的长度*/
    while(str[i]!='\0')
    {
        ++i;
    }
     strlen=i;

    /*子串最大可能长度为总字符串长度的一半，如果未找到，依次递减继续查找*/
    for(i=strlen/2;i>0;--i)
    {
        int zeronum=0;//重复字符子串个数计数
        int j;
        int k;

        for(j=i;j<strlen;++j)
        {
            /*对源字符串距离为i的字符进行比较，如果相等，计数加1，当连续计数等于i时，
            将子串以及相关参数保存；否则计数清零*/
            if (str[j]==str[j-i])
            {
                ++zeronum;
                if (zeronum==i)
                {
    memcpy(sub, str+j-2i+1, i);
    sub[i] ='\0';
    /*用上面两行代码注释下列代码
                    index1=j-2*i+1;
                    len=i;
                    for(k=0; k<len; k++)
                    {
                        sub[k] = str[index1+k];
                    }
                    sub[len] = '\0';
                    */
                    return;
                }
            }
            else
            {
                zeronum=0;
            }
        }
    }
}

int main()
{
     char str[BUF_MAX];
     char sub[BUF_MAX];

     scanf("%s",str);
     str_search(str,sub);

     printf("%d:%d\n",index1,len);
     printf("sub string:\n");
     printf(sub);
     printf("\n");
    return 0;
}

 

2.在字符串中查找子串并返回子串的位置

实现代码如下：

 

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

char *substr_search(const char *s1, const char *s2, int *postion)
{
    int n = 0;
    int pos = 0;

    /*判空*/
    if(*s2)
    {
       /*匹配s2,如果未完全匹配，当s1指针更新到字符串末尾时循环退出*/
        while(*s1)//if(*s1),曾在此处犯下低级错误，希望读者不再重蹈覆辙.
        {
                /*匹配子串s2,如果能够连续匹配s2到字符串尾，则保存偏移的位置，返回此位置开始的
                  一段字符串;否则更新计数pos,更新源字符串的值s1*/
                for(n=0; *(s1+n)==*(s2+n); n++)
                {
                    if(*(s2+n+1) == '\0')
                    {
                        *postion = pos;
                        return (char *)s1;
                    }
                }

                pos++;
                s1++;
        }

        printf("couldn't been found the sub string\n");
        *postion = 0;//当不能找到子串时，将传出参数赋值为0
        return NULL;
    }
    else
    {
        printf("the s2 string is NULL\n");
        *postion = pos;
        return (char *)s1;
    }
}

int main(void)
{
    char str1[100] = "abcdefghijkl";
    char str2[100] = "fgh";
    char *tmp = NULL;
    int pos;

    printf("str1:%s",str1);
    printf("\n");
    printf("str2:%s",str2);
    printf("\n");

    tmp = substr_search(str1, str2, &pos);
    printf("the sub string postion:%d\n", pos);
    printf("return string:");
    printf("%s\n",tmp);

    return 0;
}