How to find all the strings of a brotherhood?

Question

I have a line and another text file that contains a list of lines.

We call 2 lines "brotherhood lines" when they exactly match after sorting in alphabetical order.

For example, "abc" and "cba" will be sorted into "abc" and "abc", so the original two are brotherhood. But "abc" and "aaa" are not.

So, is there an efficient way to select all fraternity lines from a text file according to one line?

For example, we also have a "abc"text file that writes like this:

abc
cba
acb
lalala

then "abc", "cba", "acb"is the answer.

Of course, “sorting and comparing” is a good attempt, but “effective”, I mean, if there is a way, we can determine which candidate line is or not the original brotherhood after processing one pass.

This is the most effective way, I think. After all, you cannot say the answer without even reading the lines of the candidate. For sorting, in most cases we need to make more than 1 pass to the candidate line. So, a hash table may be a good solution, but I have no idea which hash function to choose.

Answer 1

The most efficient algorithm I can think of:

• - . , , , . - inputStringTable
• , , , -
• -. StringTable.
• , -. brotherStringTable [character] > inputStringTable [character], ( )
• , inputStringTable brotherStringTable. - , . , .

O (nk), n - ( , , , ), k - . , , O (nk lg n), , , .

Answer 2

, , - O (N * (k + log S)), N - , k - , S - .

, ( , ). O (k + N * S). , , , k, N S.

, , , , ...

Answer 3

, , . , ?

Answer 4

, - 'a' 'z', . 26 , .

, , . , () .

-, , , , .

.

:. , .

Answer 5

, , . . , 256 ascii.

#define NUM_ALPHABETS 256
int alphabets[NUM_ALPHABETS];

bool isAnagram(char *src, char *dest) {
    len1 = strlen(src);
    len2 = strlen(dest);
    if (len1 != len2)
        return false;

    memset(alphabets, 0, sizeof(alphabets));
    for (i = 0; i < len1; i++)
        alphabets[src[i]]++;
    for (i = 0; i < len2; i++) {
        alphabets[dest[i]]--;
        if (alphabets[dest[i]] < 0)
            return false;
    }

   return true;
}

O (mn), "n"

"m",

Answer 6

• , :
  • , "", //, .

. , ( ). , ( ) .., .

Answer 7

, , . ​​ , , ( ).

:

• ( int histogram[128] )

• • c, , histogram[c]. , .

    • histogram[c]

  • , ,

/ .

Answer 8

. , , , N ( ) L ( ) , , V ( )

, KISS . , nlogn.

target = sort_characters("target string")
count = 0
foreach (word in inputfile){
   if target.len == word.len && target == sort_characters(word){
      count++
    }
 }

Answer 9

:
:

• " " ( )
• (CRC - )
• , , .

, /.

Answer 10

, , "" . -...

:

prime['a']=2;
prime['b']=3;
prime['c']=5;

, , , ,

long long key(char *string)
{
  long long product=1;
  while (*string++) {
    product *= prime[*string];
  }
  return product;
}

, , . , "", .

- O (N), . () , . , , , , .

Answer 11

. , , , ++. -, - , , , , , ( 26), . a3c2b1 abacca.

O (N ( (M, K))) N K, .

master = "abc"
wordset = "def cba accb aepojpaohge abd bac ajghe aegage abc".split()

def dictmaster(str):
    charmap = {}
    for char in str:
        if char not in charmap:
            charmap[char]=1
        else:
            charmap[char] += 1
    return charmap

def dicttrial(str,mastermap):
    trialmap = {}
    for char in str:
        if char in mastermap:
            # check if this means there are more incidences
            # than in the master
            if char not in trialmap:
                trialmap[char]=1
            else:
                trialmap[char] += 1
        else:
            return False
    return trialmap

def dicttostring(hash):
    if hash==False:
        return False
    str = ""
    for char in hash:
        str += char + `hash[char]`
    return str

def testtrial(str,master,mastermap,masterhashstring):
    if len(master) != len(str):
        return False
    trialhashstring=dicttostring(dicttrial(str,mastermap))
    if (trialhashstring==False) or (trialhashstring != masterhashstring):
        return False
    else:
        return True

mastermap = dictmaster(master)
masterhashstring = dicttostring(mastermap)
for word in wordset:
    if testtrial(word,master,mastermap,masterhashstring):
        print word+"\n"