感谢大家参与，问题已经解决，结贴给分！
StarWing83 完整给出两道题的答案，而且第一题算法复杂度比我的好，第二题都是O（n）算持平，得分13/20 （他的算法分别在50楼，40楼）
Devil_W 的确是比较厉害的，直接看出来第一题用dp算法最好，但是没有给出完整答案，给分2/20，不过还是比较佩服他，算法水平比我好多了～～～
hahayezhe 首先看出来第二题有问题，并且提出修改方案，给分5/20表示感谢～～～

1.编写一个程序，返回两个字符串的最大公串！例如，“adbccadebbca”和“edabccadece”,返回“bccade”。
2.有个数组arr[100]存放了100个数,这100个数取自1-99（此处改为0-99）,且只有两个相同的数,剩下的98个数不同,写一个搜索算法找出相同的那个数的值.（注意空间效率时间效率尽可能要低）.
发现有些兄弟的代码没有经过测试就发上来，下面给个测试方法，以便大家写好代码后测试一下：
1. 编译成可运行程序a.out,测试命令： ./a.out adbccadebbca edabccadece
返字符串：bccade
2.补全下面代码中的search_same(int arr[], int n);定义，（假设arr[]中随机存0-99数字，34没有出现，58出现2次，其他数字出现1次，用search_same函数找出重复数字58）

#include <stdio.h>

int search_same(int arr[], int n);

int main()
{
    int arr[100];
    int i;

    for(i=0; i<100; i++){
        arr[i] = i;
    }
    arr[34] = 58;

    fprintf(stdout, "The same one:%d\n", search_same(arr, 100));

    return 0;
}

我已经写了自己的代码放在附件里面，不过是加密的，过几天给密码；
给分条件，算法空间效率和时间效率比我写的更好。 附件密码：done!
恩，请给出大致思路，以便大家更容易看懂~~~~
哈哈，没想到有这么多人回帖，先谢谢大家了。

附件密码已经发了，就在附件后面（纯白颜色的字体），请ctrl+a全选就看见了。
其实这些题是网上没事的时候搜到的，原来一共十几道，感觉这两道比较有意思，所在放上来了~~~~~

十楼的兄弟，你太强了，我看了几天咋就没想到是这么回事的呢，感叹！~~~~，说声佩服~~~(已经按照11楼的修改题目)

我的算法思路：
1.最简单的方法是一一比较，大致次数是 关于F的函数，F( strlen(str1) + strlen(str1)*strlen(str2) );想一下，有很多重复比较的，最好是扫描一次str2,然后把所有127个字符的位置存储在一个单链表数组listarr[127]中，字符的数值就是对应的数组下标；这样str1通过listarr与str2对应的字符比较，一共只需F( strlen(str1) + strlen(str2)*2 );就可以了。-----算法复杂度：最大O(n^2)，空间复杂度O(n)。

2.恩，尽量少空间，所以方法如下：从头扫描数组，并用value = arr[i]%100来取元素值，然后，检查arr[value]是否大于100，如果是那就是这个数，如果不是就把arr[value] += 100；--------算法复杂度：O(n),空间复杂度：O(1),
其实原理还是做标记，但是用原来的数+100，然后用模100取值，这样做标记空间占用几乎是0。
（题目修改后这个思路同样适用）

我的代码已经发在22楼，由于题目修改，第二题稍做修改。思路就是我上面写的~~~

[ 本帖最后由 wsj3000 于 2010-5-3 12:17 编辑 ]

（1）请您先运行通过再贴上来吧，我运行了下一大堆报错；
（2）建议时间复杂度上再优化下吧~~~~~

题目我也是在网上找到的，原题就是这样的，可能是要考您的洞察能力吧~~~，不太清楚；这可能是最简单的方法了~~~~

恩，，没话说了，我居然没有发现这个，汗~~~，不好意思，按你说的改了。~~~ths

不好意思，看不懂c++；恩，说下大致思路好吗？

恩，第二题的思路：
第2个题目，直接顺序查找，如果先查A[0], 假设A[0]=k,接着查A[k],并把A[0]做个mark，表示查过了。
接着再差A[A[k]]以此类退，重复Mark的那个就是重复的数字了。

按照你的思路，如果k=0呢？ 或则A[A[k]]=0呢，又回去查啊A[0]了，还好打了标记，所以可以继续向后查，但是却重复查找了！
应该是从a[0]到a[99],把a[k]打标记，而且打标记的方法是加上模100，取得时候全部按模100取值，然后哪个取值前大于等于100了，就是重复的那个。

[ 本帖最后由 wsj3000 于 2010-5-1 23:28 编辑 ]

是的，我这么想，不过新建数组存储mark空间就太浪费了，直接在原数组取模会节省空间一下。

我的代码：
第一题：

//file name: mcstr.c
//feature: get the max common substring from two strings;
//author: wushujie
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LISTARR_MAX 127 //the length of listarr;

typedef struct list_t list_t; //list made of node_t;
typedef struct node_t node_t; //node;
typedef struct maxstr_t maxstr_t; //information of max common string;
struct list_t{
    node_t *head; //head point to list;
};
struct node_t{
    char *pstr; //point to the proper character of str1;
    node_t *next; //point to the next node;
};
struct maxstr_t{
    int len;
    //len: length of max common string;
    char *str; //point to where the common max string from in str1;
};

#define LISTARR_HASH(x) ((x)-'\0') //get the correct position of listarr;
int preproc(char *str, list_t listarr[]);
int getmaxcom(char *str, list_t listarr[], maxstr_t *pmaxstr);
int listarr_init(list_t listarr[]);
int listarr_destroy(list_t listarr[]);
node_t *list_insert(list_t *list, node_t *pnode);
node_t *make_node(char *str);
//=======================================================

int main(int argc, char *argv[])
{
    if(argc != 3){
        fprintf(stderr, "arguments error!\n"
                "usage:\n"
                "    ./mcstr strings1 strings2\n");
        exit(1);
    }

    list_t listarr[LISTARR_MAX];
    maxstr_t maxstr = {0, argv[1]};

    listarr_init(listarr);
    preproc(argv[1], listarr);
    getmaxcom(argv[2], listarr, &maxstr);
    listarr_destroy(listarr);

    maxstr.str[maxstr.len] = '\0';
    fprintf(stdout, "%d  \"%s\"\n", maxstr.len, maxstr.str);

    return 0;
}

int preproc(char *str, list_t listarr[])
{
    while(str[0] != '\0'){
        list_insert( &listarr[LISTARR_HASH(str[0])],
                make_node(&str[0]));
        str++;
    }

    return 0;
}

int getmaxcom(char *str, list_t listarr[], maxstr_t *pmaxstr)
{
    node_t *curnd = NULL;
    int laloc = 0,
        i = 0;
    //traverse_str(str);
    while(str[0] != '\0'){
        laloc = LISTARR_HASH(str[0]);
            //traverse_list(listarr[loc]);
            for(curnd=listarr[laloc].head;
                    curnd != NULL; curnd = curnd->next){
                //compare(str, curnd->pstr);
                for(i=0; str[i] != '\0' && str[i]==curnd->pstr[i]; i++);
                if(i > pmaxstr->len){
                    pmaxstr->len = i;
                    pmaxstr->str = &str[0];
                }
            }
        str++;
    }

    return 0;
}

int listarr_init(list_t listarr[])
{
    int i;
    for(i=0; i<LISTARR_MAX; i++){
        listarr[i].head = NULL;
    }

    return 0;
}

int listarr_destroy(list_t listarr[])
{
    node_t *curnd, *next;
    int i;
    for(i=0; i<LISTARR_MAX; i++){
        curnd = listarr[i].head;
        while(curnd != NULL){
            next = curnd->next;
            free(curnd);
            curnd = next;
        }
    }

    return 0;
}

node_t *list_insert(list_t *list, node_t *pnode)
{
    pnode->next = list->head;
    list->head = pnode;

    return pnode;
}

node_t *make_node(char *str)
{
    node_t *pnode = malloc(sizeof(node_t));
    if(pnode == NULL){
        fprintf(stderr, "no memory!");
        exit(2);
    }

    pnode->pstr = str;
    pnode->next = NULL;

    return pnode;
}

第二题：

//file name:search_same.c
#include <stdio.h>

int search_same(int arr[], int n);

int main()
{
    int arr[100];
    int i;

    for(i=0; i<100; i++){
        arr[i] = 100 - i;
    }
    arr[0] = 0;
    arr[34] = 23;

    fprintf(stdout, "The same one:%d\n", search_same(arr, 100));

    return 0;
}

int search_same(int arr[], int n)
{
    int i, value;
    for(i=0; i<n; i++){
        value = arr[i]%n;
        if(arr[value]>=n){
            return value;
        }else{
            arr[value] += n;
        }
    }

    return -1;
}

[ 本帖最后由 wsj3000 于 2010-5-2 19:59 编辑 ]

是arr[100]中存了0-99个数，其中数字a不在里面，数字b出现的两次，要求求b。不是那么容易吧？主要是开始的时候，a，b你都不知道谁呀。
你上面假设a在里面是不对的。

[ 本帖最后由 wsj3000 于 2010-5-1 22:01 编辑 ]

汗～～～，这样吧,举个例子：
假设0-99中， 23不存在，位置被24代替，也就是说，0个23，2个24，其他数字都是1个，请问怎么算出来是24。
按照你的方法数组变成101个， 然后这样算， 数组和 - 4950 = 所求数；
事实上，101数组和 你是没法求出来的，因为给你的只有100个元素，而且你不知道地101个元素该取哪个。

32楼：
这样吧，你补全下面的search_same(int arr[], int n);函数的定义：

#include <stdio.h>

int search_same(int arr[], int n);

int main()
{
    int arr[100];
    int i;

    for(i=0; i<100; i++){
        arr[i] = i;
    }
    arr[34] = 58;

    fprintf(stdout, "The same one:%d\n", search_same(arr, 100));

    return 0;
}

上面缺失34，重复58，请写出你的算法找出重复的数58.

33楼：
我编译了你写的程序，用 ，“adbccadebbca”和“edabccadece”测试，得到结果：dbccadec
恩，这个结果是不对的，可以看出来正确的是：bccade 建议你再改改代码，正确了再发上来好吗？