12 ms in c,little My first Question


  • -2
    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};
    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) {
    int wordLen = strlen(words[0]);
    memset(Fingerprint1,0,sizeof(unsigned long long)wordLen);
    memset(Fingerprint2,0,sizeof(unsigned long long)wordLen);
    int wordnum=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);
    }
    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;
    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];
    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];
    if(Fingerprint1[j]==Key1&&Fingerprint2[j]==Key2){
    ReturnArray[retsize]=i-wordnum+wordLen;
    retsize++;
    }
    }
    }
    }
    *returnSize = retsize;
    return ReturnArray;
    }


  • 0
    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};
    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) {
    int wordLen = strlen(words[0]);
    memset(Fingerprint1,0,sizeof(unsigned long long)wordLen);
    memset(Fingerprint2,0,sizeof(unsigned long long)wordLen);
    int wordnum=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);
    }
    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;
    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];
    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];
    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.