16ms C,beat 100%,can be more fast .


  • -3
    K

    unsigned long long Mytable1[]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137};
    #define worldsMax 4294967295
    static unsigned long long Fingerprint1[10000];
    static unsigned long long Fingerprint2[10000];
    unsigned long long StringMap1[10000];
    unsigned long long StringMap2[10000];
    int ReturnArray[100];
    unsigned long long myHash1(char s,int size){
    unsigned long long a=0;
    int i=0;
    for(;i<size;i++){
    a=(a
    26+Mytable1[s[i]-'a']);
    }
    return a;
    }
    unsigned long long myHash2(char *s,int size){

    unsigned long long a=0;
    int i=0;
    for(;i<size;i++){
    	a=(a*27+Mytable1[s[i]-'a'+4]);
    }
    return a;
    

    }
    int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {
    memset(Fingerprint1,0,sizeof(unsigned long long)10000);
    memset(Fingerprint2,0,sizeof(unsigned long long)10000);
    int wordnum=0;
    int wordLen = strlen(words[0]);
    unsigned long long H1=1;
    unsigned long long H2=1;
    for(wordnum=wordLen;wordnum>1;wordnum--){
    H1 = H1
    26;
    H2 = H2
    27;
    }
    wordnum=0;
    returnSize=0;
    int StrMapSize1=0;
    int StrMapSize2=0;
    int i=0;
    int j=0;
    int retsize=0;
    char temp;
    unsigned long long Key1=0;
    unsigned long long Key2=0;
    for(temp=words[0];wordnum<wordsSize;wordnum++,temp=words[wordnum]){
    Key1 = Key1+myHash1(temp,wordLen);
    Key2 = Key2^myHash2(temp,wordLen);
    }
    // printf("Key1 = %lld\n",Key1);
    // printf("Key2 = %lld\n",Key2);
    StringMap1[StrMapSize1] = myHash1(s,wordLen);
    StringMap2[StrMapSize2] = myHash2(s,wordLen);
    StrMapSize1++;
    StrMapSize2++;
    for(i=wordLen;i<strlen(s);i++){
    StringMap1[StrMapSize1] =26
    (StringMap1[StrMapSize1-1]-H1
    Mytable1[s[i-wordLen]-'a']) + Mytable1[s[i]-'a'];
    StringMap2[StrMapSize2] =27*(StringMap2[StrMapSize2-1]-H2Mytable1[s[i-wordLen]-'a'+4]) + Mytable1[s[i]-'a'+4];
    StrMapSize1++;
    StrMapSize2++;
    }
    wordnum = wordsSize
    wordLen;
    // printf("StrMapSize1=%d\nwordnum=%d\n",StrMapSize1,wordnum);
    // printf("Fingerprint1[0]=%lld\n",Fingerprint1[0]);
    // for(i=0;i<StrMapSize1;i++){
    // printf("StringMap1[%d]=%lld\n",i,StringMap1[i]);
    // printf("StringMap2[%d]=%lld\n",i,StringMap2[i]);
    // }
    for(i=0;i<StrMapSize1;){
    for(j=0;i<StrMapSize1&&j<wordLen;j++,i++){
    if(i<wordnum){
    Fingerprint1[j]=Fingerprint1[j]+StringMap1[i];
    Fingerprint2[j]=Fingerprint2[j]^StringMap2[i];
    // printf("1-Fingerprint1[%d]=%lld\n",j,Fingerprint1[j]);
    // printf("1-Fingerprint2[%d]=%lld\n",j,Fingerprint2[j]);
    if(i>=(wordnum-wordLen)&&Fingerprint1[j]==Key1&&Fingerprint2[j]==Key2){
    ReturnArray[retsize]=i-wordnum+wordLen;
    retsize++;
    }
    }else{
    Fingerprint1[j]=Fingerprint1[j]-StringMap1[i-wordnum]+StringMap1[i];
    Fingerprint2[j]=Fingerprint2[j]^StringMap2[i-wordnum]^StringMap2[i];
    // printf("2-Fingerprint1[%d]=%lld\n",j,Fingerprint1[j]);
    // printf("2-Fingerprint2[%d]=%lld\n",j,Fingerprint2[j]);
    if(Fingerprint1[j]==Key1&&Fingerprint2[j]==Key2){
    ReturnArray[retsize]=i-wordnum+wordLen;
    retsize++;
    }
    }
    }
    }
    *returnSize = retsize;
    return ReturnArray;
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.