I have some strings, ex:
A[10] = "message";
B[25] = "AAmSSeDDsFFsGGaHHgJJe";
C[10] = "messaeg";
So i need some ideas for finding substrings like this: in the example, A is substring of B coz with eleminating some characters (only eleminating, not moving their place!) we can get string A, and A is not substring of C.
I have tried with strncmp() and strchr() but no success.
Any ideas about this ?
You should post your code for people to see where you went wrong.
You could use a loop which does strchr() to find the a particular character, and if you find that character, search from that position onwards for the next character, and so on. If you find the end of the "needle" string, then you have a substring by your definition.
And by lucky coincidence, strchr() returns a pointer to the string you want to search for, so you could just use that for the next string - just make sure that if strchr() returns NULL, you end the search.
--
Mats
Compilers can produce warnings - make the compiler programmers happy: Use them!
Please don't PM me for help - and no, I don't do help over instant messengers.
Based solely on what you've posted, I'm guessing that what you've failed to take into account is that you must start searching for character 2 from the place where you found character 1, and not from the start of the string.
I did not go wrong anywhere because i don't even have the code - i was asking for some ideas how to solve the problem, that's all.Originally Posted by blurx
@matsp:
Thanks matsp, you gave really good ideas.
One is forced to wonder how you tried strncmp and strchr if you don't even have code.
OK, so I am stuck in here again.
I have tried to solve this problem, but with no success. I tried the matsp's idea and i think that i implemented it well, but i have no results on strings with characters that are repeating.
Here is the code:
Code:#include <stdio.h> #include <string.h> int main() { int y, x[100], i, j = 0, k, n, z, g = 0; char a[251], b[251]; FILE *file; file = fopen("text.txt", "r"); fscanf(file, "%d", &n); for(i = 0;i < n;i++) { fscanf(file, "%s %s", a, b); y = strlen(a); z = strlen(b); for(k = 0;k < y;k++) { for(j;j < z;j++) { if(a[k] == b[j]) { x[k] = j; j++; break; } } printf("x%d-[%d] = %d\n", i, k, x[k]); } } fclose(file); return 0; }
Depends if repeating characters are considered valid and part of the string.
Yes, it is allowed to have repeating characters in the string. Ex:
message IS substring of mmmeeesssssssgggaaagggeeeeggggwwwaaassseee
Some help about this ?
Why is that any different than normal processing?
Just skip o'er the duplicates until a matching char is found?
Make sure to advance the pointer to the next char on the substring.
The problem is that anything i try simply does not give me any positive result.
Here is the code of what i have tried to do, based on the idea you gave.
Still no results.
Code:#include <stdio.h> #include <string.h> int main() { int i, n, k, c, d[251], y, z , j = 0, u = 0, r = 0; char a[251], b[251]; FILE *file; file = fopen("text.txt", "r"); fscanf(file, "%d", &n); for(i = 0;i < n;i++) { fscanf(file, "%s %s", a, b); y = strlen(a); z = strlen(b); for(k = 0;k < y;k++) { for(j;j < z;j++) { if(a[k] == b[j]) { if(j = d[k]) break; d[k] = j; j++; } } printf("d[%d] = %i\n", k, d[k]); } } fclose(file); return 0; }
Can you explain the code as it's not very obvious which is the string and which is the substring.
Note that the pointer over the substring doesn't move until a match is found but not so for the string.
b is the string (the larger one), and a should be substring of b.
I suggest that you simplify your test program:
Without loss of generality, implement juxtaposeFind() in the above program such that you pass both test cases (and more, which can easily be added via the testFound() and testNotFound() functions). Once you are certain that your algorithm and its implementation are correct, you can then add the code that reads from a file.Code:#include <stdio.h> int juxtaposeFind(const char *search, const char *subject); void testFound(const char *search, const char *subject); void testNotFound(const char *search, const char *subject); int main(void) { testFound("message", "AAmSSeDDsFFsGGaHHgJJe"); testNotFound("messaeg", "AAmSSeDDsFFsGGaHHgJJe"); return 0; } int juxtaposeFind(const char *search, const char *subject) { /* ... */ } void testFound(const char *search, const char *subject) { printf("%s\n", juxtaposeFind(search, subject) ? "pass" : "fail"); } void testNotFound(const char *search, const char *subject) { printf("%s\n", !juxtaposeFind(search, subject) ? "pass" : "fail"); }
Last edited by laserlight; 03-07-2009 at 03:04 PM.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
Here's how the algorithm looks like:
Code:read in substring a and string b set a's index to zero for loop (until b's end) if (elements of a and b match) increment a's index by one, and if (a[index] is NULL) print match found and exit print match not found and exit
Last edited by itCbitC; 03-07-2009 at 03:06 PM.
