Thread: Returning Correspond Matrix to problem rules

  1. #1
    Registered User
    Join Date
    Nov 2020
    Posts
    34

    Returning Correspond Matrix to problem rules

    Hi ;
    Im trying to implement in c a function that's called Sniffer which gets two inputs and returns the correspond matrix.
    First input is an integer binary array values (just zero or one)
    second input is your searched word ( the word you choose it as argument to your function )
    the functionally of the function ( what the function does) :
    searching for occurrence of the given word within your given binary array. at each occurrence of your word there's always follows 8 bits following it, assume that always the input is correct (it means that there's no possibility two occurrence occur one after the other without at least there's space 8bits (8 binary values)!). then the function must return a matrix(integer matrix) of those followed 8bit for each occurrence of the word sorted corresponded by every row of the matrix. (the functions returns just the first 8bit followed each occurrence of the Searched word)
    this means:
    First row has first 8 followed bit on first occurrence of the word.
    Second row has first 8 followed bit on second occurrence of the word.
    Third row has first 8 followed bit on third occurrence of the word.
    Fourth row has first 8 followed bit on fourth occurrence of the word.
    etc ...

    I will elaborate by examples:
    function structure is
    Code:
    int ** SnifferPattern(int* givenArray ; int* SearchedWord);
    //it returns the corresponded matrix so used int** ;
    #1
    Code:
    givenArray={1,0,1,0,1,1,1,1,1,1,1,1,0,0};
    SearchedWord={1,0,1,0};
    so the function returns a matrix(size 1x8 - 8 corresponds to 8followed bit) the first row is
    {1,1,1,1,1,1,1,1} which it's the first 8 bit followed the word 1010
    the matrix here with one row because there's just one occurrence
    of the SearchedWord in the given array.
    example 2:
    #2
    Code:
    givenArray={1,1,0,0,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1,0,1,0};
    SearchedWord={1,1,0,0}
    so the function returns a matrix the first row is
    {1,1,1,1,1,1,1,1} which it's the first 8 bit followed the word 1010 for the first occurrence.
    for the second occurrence we see the word appear , so the second row of the returned matrix(size 2x8) will include the first 8bit followed the word 1010 of the second occurrence. so second row of the matrix is
     {1,0,1,0,1,0,1,0}
    so the returned matrix (size 2x8) has two rows (because there's two occurrences of the SearchedWord) which each row corresponds to each occurrence of the SearchedWord.
    third example:
    #3
    Code:
    givenArray={1,1,1,0,1,1,1,1,1,1,1,1,0,0};
    SearchedWord={0,1,0}
    so the function returns a matrix zero row (like an array with zero values) size 1x8 (8 columns is corresponded to 8followed bit).
    there's no occurrence of the SearchedWord within the givenArray so we return a zero matrix.
    There's no overlap between the occurrences of the searchedWords , so we assume always correctness of input.


    I will explain my algorithm (a pleasure if there's another suggestions more compatible to my case)
    My algorithm is searching for the word by binary search and then take at every occurrence the first followed 8bit . but it sounds much hard to complete with this.
    I implemented the binary search and I'm stuck how to continue in order to get correct outputs (matrix of the first followed 8bit at each occurrence of the searched word) :
    Code:
    void binary_search(int* givenArray, int* target){
        int bottom= 0;
        int mid;
        int top = size - 1;
    
    
        while(bottom <= top){
            mid = (bottom + top)/2;
            if (strcmp(&givenArray[mid], target) == 0){
                printf("%s found at location %d.\n", target, mid+1);
                break;
            }
            if (strcmp(&givenArray[mid], target) == 1){
                top= mid - 1;
            }
            if (strcmp(&givenArray[mid], target) == -1){
                bottom= mid + 1;
            }
        }
    }
    
    
    int main(){
    
    
        int givenArray[14]={1,0,1,0,1,1,1,1,1,1,1,1,0,0}; //given array 
        int SearchedWord[4]={1,0,1,0} //given word to search about it within given array
        int i = 0;
       binary_search(givenArray, SearchedWord);
        return 0;
    }
    Any help in this please? maybe converting the binary array values to string will make the implementation more easy? I feel that the problem is trivial and easy but I went to complex approach that will take to much time to implement.

    Appreciate for any help guys - much thanks.

  2. #2
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    Would it also be correct to say.. .

    You are looking for sequences, 'ppppddddddd' , where 'p' is the known prefix (that in this case has a length of four) , and 'd' is 8 data values that needs to be returned to the caller?

    For example you might search for 1010xxxxxxxx.

    If this is the case, then a binary search is not the right way to do it - a '12 entry sliding window' is the more appropriate option.

  3. #3
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Quote Originally Posted by hamster_nz View Post
    Would it also be correct to say.. .

    You are looking for sequences, 'ppppddddddd' , where 'p' is the known prefix (that in this case has a length of four) , and 'd' is 8 data values that needs to be returned to the caller?

    For example you might search for 1010xxxxxxxx.

    If this is the case, then a binary search is not the right way to do it - a '12 entry sliding window' is the more appropriate option.
    Yes exactly this what I'm looking for but be careful if the searched word occurrence once then at least there's 8bits appear before the next occurrence of the searched word(in your example you wrote pppp which it's not possible in my case ..just one p occur then the other could occur after at least 8bit between the first and second occurrence of Searched word).


    for your last sentence what do you mean? could you please instruct me because Im stuck.

    appreciated.

  4. #4
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    Simple implementation... (sorry for typos on phone)

    Code:
    x = 0;
    while ( x < input_len - 8 - prefix_len) 
    {
       If prefix seen at position x 
       {
          Grab 8 bits starting from x+prefix_len to add to output;
          x += prefix_len + 8;
       }  else {
          x++;
       } 
    }

  5. #5
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Quote Originally Posted by hamster_nz View Post
    Simple implementation... (sorry for typos on phone)

    Code:
    x = 0;
    while ( x < input_len - 8 - prefix_len) 
    {
       If prefix seen at position x 
       {
          Grab 8 bits starting from x+prefix_len to add to output;
          x += prefix_len + 8;
       }  else {
          x++;
       } 
    }
    I understand, but here you're not searching for the searched word , didn't I explain the question in a good way? because maybe you missunderstand the question. so what you attached don't help me ..

    My problem is that I need to search for the the searched word within the array and at every occurrence of the searched word in the array I there would be a row matrix have the 8bit followed the searched word at each occurrence correspondingly.


    Hope now is more understandable.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    That pseudocode does search for the word: that search is described by "If prefix seen at position x". It can be a simplistic loop that checks if there's an exact match. If there's a mismatch, increment the search index by 1 (hence the x++) and repeat the loop.

    Quote Originally Posted by JohnnyOmari
    in your example you wrote pppp which it's not possible in my case ..just one p occur then the other could occur after at least 8bit between the first and second occurrence of Searched word
    You have to understand that "ppppddddddd" was used in the same way that some people might describe a date format as "yyyy-mm-dd". It doesn't mean that "p" refers to a particular value, and hence "pppp" must mean either "0000" or "1111", but rather that it is a placeholder for some value -- any valid value -- that forms part of the "prefix". So, it can stand in for "0000", or "0001", or "0010", or "0011", "0100", "0101" etc. Hence, by your description of the problem it is impossible for "just one p occur then the other could occur after at least 8bit between the first and second occurrence of Searched word", because "pppp" is the "searched word".
    Last edited by laserlight; 01-01-2021 at 08:03 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Quote Originally Posted by laserlight View Post
    That pseudocode does search for the word: that search is described by "If prefix seen at position x". It can be a simplistic loop that checks if there's an exact match. If there's a mismatch, increment the search index by 1 (hence the x++) and repeat the loop.


    You have to understand that "ppppddddddd" was used in the same way that some people might describe a date format as "yyyy-mm-dd". It doesn't mean that "p" refers to a particular value, and hence "pppp" must mean either "0000" or "1111", but rather that it is a placeholder for some value -- any valid value -- that forms part of the "prefix". So, it can stand in for "0000", or "0001", or "0010", or "0011", "0100", "0101" etc. Hence, by your description of the problem it is impossible for "just one p occur then the other could occur after at least 8bit between the first and second occurrence of Searched word", because "pppp" is the "searched word".

    I understand you much! , thanks alot.
    but my problem is what the algorithm to use for grabbing each 8followed bit after each occurrence of SearchedWord and storing them in the matrix(at the end I return the matrix) .. here's my catch!

    Any suggestion? for instance in C++ there's an already built function called find but in c there's no function called find that I can call it!


    Appreciate for your help in advance.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    but my problem is what the algorithm to use for grabbing each 8followed bit after each occurrence of SearchedWord and storing them in the matrix(at the end I return the matrix) .. here's my catch!
    If you already found the word, grabbing the 8 bits is just a matter of computing where they start and copying them.

    Any suggestion? for instance in C++ there's an already built function called find but in c there's no function called find that I can call it!
    Write it. If you find it too hard, work on a simplified version of this problem, i.e., all you're interested in is finding the very first instance of the word. No 8 bits, no matrix. Refer to posts #2, #4 and #6 to help you because those contain the very suggestions that you're asking for.
    Last edited by laserlight; 01-01-2021 at 11:57 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    Quote Originally Posted by laserlight View Post
    That pseudocode does search for the word: that search is described by "If prefix seen at position x". It can be a simplistic loop that checks if there's an exact match. If there's a mismatch, increment the search index by 1 (hence the x++) and repeat the loop.


    You have to understand that "ppppddddddd" was used in the same way that some people might describe a date format as "yyyy-mm-dd". It doesn't mean that "p" refers to a particular value, and hence "pppp" must mean either "0000" or "1111", but rather that it is a placeholder for some value -- any valid value -- that forms part of the "prefix". So, it can stand in for "0000", or "0001", or "0010", or "0011", "0100", "0101" etc. Hence, by your description of the problem it is impossible for "just one p occur then the other could occur after at least 8bit between the first and second occurrence of Searched word", because "pppp" is the "searched word".
    Quote Originally Posted by JohnnyOmari View Post
    I understand, but here you're not searching for the searched word , didn't I explain the question in a good way? because maybe you missunderstand the question. so what you attached don't help me ..

    My problem is that I need to search for the the searched word within the array and at every occurrence of the searched word in the array I there would be a row matrix have the 8bit followed the searched word at each occurrence correspondingly.


    Hope now is more understandable.
    Quote Originally Posted by laserlight View Post
    If you already found the word, grabbing the 8 bits is just a matter of computing where they start and copying them.


    Write it. If you find it too hard, work on a simplified version of this problem, i.e., all you're interested in is finding the very first instance of the word. No 8 bits, no matrix. Refer to posts #2, #4 and #6 to help you because those contain the very suggestions that you're asking for.
    Alright as you wish, lets take part part till we succeed !

    Now, Im trying to implement the part that finding each occurrence of given SearchedWord within the given array.

    What I tried to write in C is this program (the program prints the first location at each occurrence of the SearchedWord within the given array) :
    bear with me please till we succeed to implement this part and then we move on!.
    Code:
    int main()
    {
        int s[1000]={1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1}, w[1000]={1,0,1}; //s is the given array, w is the searched Word , number occurrences      //here 2 , so it should be two prints on the output of the program.
        int n, a[1000], i=0, j, k = 0, l, found = 0, t = 0;
        a[k++] = i;
        j = 0;
        for (i = 0; i < k; i++)
        {
            n = a[i] - j;
            if (n == (sizeof(w)/sizeof(w[0])))
            {
                t = 0;
                for (l = 0; w[l]; l++)
                {
                    if (s[l + j] == w[l])
                    {
                        t++;
                    }
                }
                if (t == (sizeof(w)/sizeof(w[0])))
                {
                    found++;
                    printf("word occurred at location=%d \n", j);
                }
            }
    
    
            j = a[i] + 1;
        }
    
    
    }
    Yes this is what I arrived after implementing a code , So what's wrong with it? why Im not getting correct output as I explained above?

    thanks for any help.

  10. #10
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    Sizeof() gives the size of the array, not the size of the initialized items.

    So you are tooping to 1000.

  11. #11
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    Oh and in the nested for loop the expression for when to keep looping seems wrong.

    It will stop when the element in w is zero.

  12. #12
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    And also, what is the value of 'k' in the topmost for loop?

  13. #13
    Registered User
    Join Date
    Sep 2020
    Posts
    425
    Code with my analysis

    Code:
    // Where is "#include <stdio.h>"???
    
    
    int main()
    {
        // Let the compiler work out the size of the storage required
        // This will also allow sizeof() to get the expected results
        int s[1000] = {1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1};
        int w[1000] = {1,0,1}; 
    
    
        // s is the given array, w is the searched Word , number occurrences      
        // here 2 , so it should be two prints on the output of the program.
    
    
        int n;          // Why is n here, what is its use?
        int a[1000];    // Why is it sized to 1000?
        int i=0;        // Why set it to zero here and also at the start of the 'for' loop? 
        int j;          // What is j used for?
        int k = 0;      // No idea what 'k' is!
        int l;          // l seems to be used in the inner loop, for checking match
        int found = 0;  // I know what this is!
        int t = 0;      // Count of matching characters in inner loop
    
    
        a[k++] = i;  // No idea what this does
        j = 0;       
        for (i = 0; i < k; i++) // 'k' is zero, so the loop will not run.
        {
            n = a[i] - j;   // Makes no sense?
            if (n == (sizeof(w)/sizeof(w[0])))  // Makes no sense, because n is nonsensical.
            {
                t = 0;
                for (l = 0; w[l]; l++)  // Condition is wrong. 
                {
                    if (s[l + j] == w[l])
                    {
                        t++;  // Matched a character.
                    }
                }
               
                if (t == (sizeof(w)/sizeof(w[0])))  // If all characters match
                {
                    found++;  // We found a match!
                    printf("word occurred at location=%d \n", j);  // Pint location
                }
            }
     
     
            j = a[i] + 1; // No idea what this is doing
        }
     
    }

  14. #14
    Registered User
    Join Date
    Nov 2020
    Posts
    34
    I would much appreciate @laser about the direction on the solution, he's really pro-tutor ... I succeeded to implement the function! thanks alot !!!

    thank you all for the assistance, appreciate.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 05-19-2014, 07:32 PM
  2. Returning a double matrix
    By adarpodracir in forum C Programming
    Replies: 5
    Last Post: 03-25-2012, 03:20 PM
  3. Problem Returning Value
    By CProgramming11 in forum C Programming
    Replies: 12
    Last Post: 11-21-2010, 11:27 AM
  4. Matrix Problem
    By TheJones in forum C Programming
    Replies: 2
    Last Post: 11-01-2006, 11:34 AM
  5. Returning a Matrix
    By Shamino in forum C++ Programming
    Replies: 14
    Last Post: 02-25-2006, 01:36 AM

Tags for this Thread