Efficient string comparison

Question

I have been trying to implement an efficient string comparing algorithm that will given points according to character changes.

For example:

String #1: abcd  
String #2: acdb  
Initial Point: 0

In here String #2 character c changed it's index from 2 to 1, and d changed its index from 4 to 3. Both of them (2-1=1 and 4-3=1) adds up to 2 points to initial point. Not a homework or anything, I just didn't want to create a basic for loop comparing each character one by one and wanted to ask if anything efficient method (like hashing etc.) can be applied?

The question is unclear, but maybe you're thinking about something like "edit distance" or "Levenshtein distance". — Kerrek SB
– Kerrek SB, Commented Dec 24, 2011 at 14:27
What exactly are you searching for again? Also can the string have repeating characters? And if so how do you know which 'c' from the second string is the 'c' from the first one? — Ivaylo Strandjev
– Ivaylo Strandjev, Commented Dec 24, 2011 at 14:49

Matteo Italia · Accepted Answer · 2011-12-24 14:29:02Z

3

You are overcomplicating a simple thing. You can't get more efficient than comparing each character and stopping the comparison at the first character you find different - which is basically what strcmp does. The only typical optimization you can do is, if you already know the length of the two strings (as happens when you use std::string or other counted strings), to determine them unequal immediately if the two length differ.

answered Dec 24, 2011 at 14:29

Matteo Italia

128k18 gold badges219 silver badges313 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ali Over a year ago

The reason why I am persisting on an efficient solution instead of an easy string comparizon is because I have to calculate the string changes for each permutation of the String #1. If the string is 'abc' I have calculate for 'acb','bca','bac','cab','cba'

Philipp Over a year ago

@roland: What exactly are you trying to achieve? To test whethe two strings are permutations of each other, you can e.g. count how often each character appears in the strings. The strings are permutations of each other iff all their character counts are equal.

Mike Dunlavey · Accepted Answer · 2011-12-24 16:32:19Z

It sounds like what you really want is something like Levenshtein distance (but not exactly that). Here's a first cut.

What it does is walk the game tree of all possible rearrangements of a to see if they match b. It associates a cost with each rearrangement, expressed as a declining budget.

The outer loop walks first with a budget of 0, so only an exact match is allowed.

If it got no success, then it walks with a budget of 1, finding all matches containing only one rearrangement.

If it got no success, then it walks with a budget of 2, and so on.

As it matches, it keeps an array of integers delta, telling how far each element of a has been swapped. Whenever it gets a success, it somwhow prints out that delta array, and that is your record of what swaps were done to get that match.

void walk(char* a, char* b, int* delta, int budget, int& nSuccess){
  delta[0] = 0;
  if (budget < 0) return;
  if (a[0] == '\0' && b[0] == '\0'){ // end of both strings
    nSuccess++;
    // print out the deltas
    return;
  }
  if (a[0] == '\0') return; // excess chars in b
  if (b[0] == '\0') return; // excess chars in a
  if (a[0] == b[0]){ // first chars are equal, move to next
    walk(a+1, b+1, delta+1, budget, nSuccess);
    return;
  }
  for (int i = 1; a[i] != '\0'; i++){
    delta[0] = i;
    swap(a[0], a[i]);
    if (a[0] == b[0]){
      walk(a+1, b+1, delta+1, budget-1, nSuccess);
    }
    swap(a[0], a[i]);
    delta[0] = 0;
  }
}

void top(char* a, char* b){
  int nSuccess = 0;
  int delta[512];
  for (int budget = 0; nSuccess==0; budget++){
    walk(a, b, budget, delta, nSuccess);
  }
}

The performance of the algorithm is exponential in N, where N is the minimum number of rearrangements needed to make the strings match. So it probably should not be used until after you've verified that each strings has the same number of each character, and only use it if you need to see that record of rearrangements.

Collectives™ on Stack Overflow

Efficient string comparison

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related