两组字符串做比较的问题（求最佳算法）

Question

假定最多4000个子串
1. 把A分割成数组的时候，同时找一个hash算法（最好hash到一个比较小的范围里，比如1到4000，不过没有关系，大不了hash到1～65535，这种算法还是多的是），计算比如ab-123对应368...，存到数组aaa[65535]或者aaa[4000]里面去
2. 把B分割成数组，也计算他的hash值，看看aaa[xxx]是不是为0，如果为0,则这个子串没有在A种出现过，如果aaa[xxx]=n, n>0,那就和这n个子串比较
细节你自己考虑一下，我觉得这个想法可行，虽然我没有试过，也是刚刚才想出来的再探讨

Answer 1

把A分割成数组的时候，同时计算hash值，这是省时的关键因为这样A和B中的所有的子串这样的情况基本上只被扫描或者比较一遍

Answer 2

考，你连长度都不要求？
That's Easy！！！
if (0==strncmp(a,b,strlen(b)) )
{
   printf("没找到\n");
}
else if( strncmp
{
   printf(b);
}搞定！！！！！！！！！！！

Answer 3

如果我没有看错的话，你的意思是在一个字符串里面查找某几个字符，但是题目是重一组字符串里面查找某一个字符串啊！
也就是说字符串B是一个数组，strlen（b）管用吗？？？

Answer 4

看你的意思是字符串数组 char* A[],*B[];然后找出在B中而不在A中的。N为B的字符串个数
M为A的字符串个数方法一、先将A排序，然后对每一个B元素去折半查找发
时间复杂度：log2(M)*N + M*M方法二、将A、B都排序，然后从上到下一遍比较就OK了
时间复杂度：M×M＋N×N＋M＋N

Answer 5

你原来的时间复杂度应该为
M×N如果你每次都有排序的话，就可以忽略排序的时间，时间复杂度为
方法一、log2(M)*N
方法二、M+N

Answer 6

算法：
/*
设a串长度为A_LENGTH, b串长度为B_LENGTH
*/unsigned char bFlag[256];
unsigned char *A, *B; //要比较的串
int i;CString sResult = "";memset(bFlag, 0, 256);
for(i = 0; i < A_LENGTH; i ++)
    bFlag[ A[i] ] = 1;
for(i = 0; i < B_LENGTH; i ++)
    if(bFlag[ B[i] ] == 0)
        bFlag[ B[i] ] = 2;for(i = 0; i < 256; i ++)
    if(bFlag[ i ] == 2)
        sResult += (char)i;结果存在sResult串中。

Answer 7

我在上面的回复中理解的意思错了，呵呵。我觉得还是strip(阿飞)的方法比较好，HASH算法可考虑用MD5，HASH表结构用一个数组可能不行，可考虑用一些通用的HASH表结构。

Answer 8

1。对array1和array2排序排序后array1[1]>array1[2]>array1[3]>...
array2[1]>array2[2]>array2[3]>...
2在array2中查找和array1相同的字符串
if array1[1]=array2[1] then
{
 if array1[2]=array2[2]  ...
}
else 
   array1[1]=array2[2]
array1[4000]=array2[4000]
只用比4000次就可以了以上方法是否真的4000次搞定？
好像不太对啊！

Answer 9

对array1和array2排序排序后array1[1]>array1[2]>array1[3]>...
array2[1]>array2[2]>array2[3]>...
2在array2中查找和array1相同的字符串
#define NA 100
#define NB 200
char *arrA[NA], *arrB[NB];int iA = 0;
for(int iB=0;iB<NB;iB++)
{
    while( (iA<NA) &&strcmp (arrB[iB],arrA[iA]<0) ) iA++;
    if( 0==strcmp(arrB[iB],arrA[iA]) ) 
    {
    ....// arrB[iB] is belong to  arrA
    }
    else
    {
    ....
    }
}

Answer 10

Sorry, 排序应该是由小到大程序才能实用
arr[0]<=arr[1]<=...<=arr[N]

Answer 11

那有更多的关于hash 的资料.  希望具体讨论一下hash实现的方法.

Answer 12

是啊，讨论一下hash吧！！！
真的很想知道hash的解法！

Answer 13

hash算法基本上都是把随机的一大堆整数(比如0<x<n)映射到一个小的范围里面（比如0<y<m,m<n）, 最简单的hash算法，对于任意一个要hash的数x,计算x mod m, 即hash(x) = x mod m; 
比如有1,3,9,11,28 要hash到 0到7的范围里，则：
hash(1) = 1
hash(3) = 3
hash(9) = 2
hash(11) = 4
hash(28) = 0
真巧这些数hash完一个重复的都没有，如果增加一个38, hash(38) = 3 = hash(3)了这是最简单的hash算法，记得，如果在n>>m的情况下，这个m最好选个质数，原理很容易想通对于你的例子：
ab－123，cd－231，erq－475,tep-987如果采用这种比较简单的hash算法，可以这样来考虑：比如选定hash到[0-4000],由于字符串里的字符一个个相加，他们的结果肯定[0-255],对于4000个样本，这样的出的结果重复太多，也就没有必要映射到[0-4000],可以映射到[0-255],重复太多效率显然低，所以我们考虑两个字符相加，就是sum = 'ab' + "-1" + "23", sum = "er" + "q-" + "47" + "50" (erq-475后面补0好了)'ab' 是两个字节，可以看做一个整数，这样所有的子串的sum都能计算出来，这些sum一定是在[0-65535]之间（如果sum>65535取sum=sum mod 65535的话）现在变成要把[0-65535]映射到[0-4000], 因为4000<<65535, 所以我们可以在4000往上找一个质数，假设是4013, 我们要做的就变成[0-65535]映射到[0-4013] 按照开始介绍的hash方法去hash就可以了上面我讲的方法都只是例子，并不一定最适合你的情况，但我觉得够用了，如果你要更好的hash方法的话，那就自己去研究了，这里也讲不清楚你这个100分真费老了劲... 给大家加点油先？？？

Answer 14

有关HASH的，计算机的数据结构数多得去了，自己看去。希望大家多提思路和算法

Answer 15

看看算法实现
#include "stdafx.h"
#define M 10
#define N 20
#include <stdlib.h>
#include <time.h>void GetSame(int* pA,int *pB);int main(int argc, char* argv[])
{
int pA[M],pB[N];
srand(time(NULL));
pA[0] = 1;
pB[0] = 2;
printf("\npA is:\n%4d",pA[0]);
for(int i=1;i<M;i++)
{
pA[i] = pA[i-1]+rand()%6+1;
printf("%4d",pA[i]);
}
printf("\npB is :\n%4d",pB[0]);
for(    i=1;i<N;i++) 
{
pB[i] = pB[i-1]+rand()%3+1;
printf("%4d",pB[i]);
}
printf("\nthe same is:\n");
GetSame(pA,pB);
printf("\n\n");
return 0;
}void GetSame(int *pA,int *pB)
{
int j=0;
for(int i=0;i<M;i++)
{
while(j<N && pB[j]<pA[i] ) j++;
if( j>=N ) break;
if( pA[i]==pB[j] ) printf("%4d",pA[i] );
}
}