找出一个字符串中最长重复次数的子字符串，并计算其重复次数。例如：字符串“abc fghi bc kl abcd lkm abcdefg”，并返回“abcd”和2。

由于题目要求寻找至少重复2次的最长的子字符串，重点在于最长的子字符串，而不在于重复的最多次数。因此我们可以从长度最长的字符串入手，计算其重复次数。只要重复达到2次，即可返回该字符串。

#include <stdio.h>#include <stdlib.h>#include <string.h>int find_longest_dup_str(char* src, char* dest);int str_sub(char* src, char* sub, int pos,int len);int str_cnt(char* src,char* sub);int main(int argc, char* argv[]){    char str[] = "abc fghi bc kl abcd lkm abcdefg";    char sub[128] = "";    int cnt;    cnt = find_longest_dup_str(str,sub);    printf("result: %s\ncnt: %d \n",sub,cnt);}int find_longest_dup_str(char* src, char* dest){    int len;    int index;    int cnt;    for(len = strlen(src);len > 0;len--)    {        for(index = 0; index + len-1 < strlen(src); index++)        {            str_sub(src,dest,index,len);            if((cnt = str_cnt(src,dest)) >= 2)            {                return cnt;            }        }    }    return 0;}int str_sub(char* src, char* sub, int pos,int len){    int index;    for(index = 0; index < len;index++)    {        sub[index] = src[pos + index];    }    sub[index] = ‘\0‘;}int str_cnt(char* src,char* sub){    int cnt = 0;    char tmp[128];    int index;    int index_sub;    for(index = 0;index + strlen(sub)-1 < strlen(src);index++)    {        /* method1        for(index_sub = 0; index_sub < strlen(sub);index_sub++)        {            if(src[index + index_sub] != sub[index_sub])            {                break;            }        }        if(index_sub == strlen(sub))        {            cnt++;        }        */        /* method2        str_sub(src,tmp,index,strlen(sub));        if(strcmp(sub,tmp) == 0)        {            cnt++;        }        */        // method3        if(strncmp(src + index,sub,strlen(sub))== 0)        {            cnt++;        }    }    return cnt;}

自然数采用蛇形排列方式填充到数组中。将自然数1、2、3…、N*N逐个顺序插入方阵中适当的位置，这个过程沿斜列进行。将斜列编号为0、1、2…、2n（以i标记，n=N-1），如下面的数据排列，这个排列为蛇形排列。

1   3    4    10

2   5    9    11

6   8   12   15

7  13  14   16

(0,0)                                     和为0

(1,0) (0,1)                             和为1

(0,2) (1,1) (2,0)                     和为2

(3,0) (2,1) (1,2) (0,3)             和为3

(1,3) (2,2) (3,1)                     和为4      --> (0,4) (1,3) (2,2) (3,1) (4,0)

(3,2) (2,3)                             和为5      --> (5,0) (4,1) (3,2) (2,3) (1,4)

(3,3)                                     和为6      --> (0,6) (1,5) (2,4) (3,3) (4,2) (5,1) (6,0)

不难发现只要在同一斜行上的数字，其对应数组行列下标之和总是相等的。

注意，当和为4或者大于4时，填充数字时要注意越界问题，因此我在程序中特意写了一个宏来判断。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 4#define IS_LEGAL(row,col) ((row) >= 0 && (row) < N && (col) >= 0 && (col) < N )void print(int (*arr)[N]);void fill(int (*arr)[N]);int main(int argc, char *argv[]){    int arr[N][N];    memset(arr,0,sizeof(arr));    fill(arr);    print(arr);    return 0;}void print(int (*arr)[N]){    int i,j;    for(i = 0; i < N; i++)    {        for(j = 0; j < N; j++)        {            printf("%3d",arr[i][j]);        }        printf("\n");    }}void fill(int (*arr)[N]){    int sum;    int row,col;    int num = 0;    for(sum = 0; sum < 2 * N - 1; sum++)    {        if(sum % 2 == 0)        {            for(row = 0; row < N; row++)            {                col = sum - row;                if(IS_LEGAL(row,col))                {                    arr[row][col] = ++num;                }            }        }else        {            for(row = sum; row >=0; row--)            {                col = sum - row;                if(IS_LEGAL(row,col))                {                    arr[row][col] = ++num;                }            }        }    }}

#include <stdio.h>#include <stdlib.h>#include <string.h>int main(int argc, char *argv[]){    int size;    int row,col;    int num = 0;    int index;    size = atoi(argv[1]);    /* 动态分配二维数组，用于存放魔方阵 */    int **arr = (int**)calloc(size,sizeof(int*));    for(index = 0; index < size; index++)    {        arr[index] = (int*)calloc(size,sizeof(int));    }    /* 存放魔方阵 */    row = 0;    col = size >> 1;    arr[row][col] = ++num;    while(num < size * size)    {        if(num % size == 0)        {            row = (row + 1) % size;            col = col;            arr[row][col] = ++num;        }else        {            row = (row - 1 + size) % size;            col = (col + 1) % size;            arr[row][col] = ++num;        }    }    /* 打印 */    for(row = 0; row < size; row++)    {        for(col = 0; col < size; col++)        {            printf("%-3d",arr[row][col]);        }        printf("\n");    }    /* 释放存储空间 */    for(index = 0; index < size; index++)    {        free(arr[index]);        arr[index] = NULL;    }    free(arr);    arr = NULL;        return 0;}

c算法题