UVa 11732 – strcmp() Anyone?

Hello everyone , I meet you again , I'm the king of the whole stack .

The title of ： Here's something for you , Give you a string comparison function , All words are parity , What is the number of comparisons .

analysis ： string 、 terry .

First . Look at the data size , Suppose you find clues normally , meeting TLE and MLE.

because , The conventional dictionary tree depth is 1000, And there may be a lot of waste of correction space .

therefore , Adopt the compression algorithm of tree （ Brother left , The right child ）. Can improve execution efficiency .

then . The same level in the dictionary tree can . In Statistics , Be able to make achievements before making statistics , Or make statistics while building trees .

Here I choose the method of statistics while building trees （ A large number of online practices , They are built first and then counted , Search for solutions ）

Every time you insert a word . It is only compared with the words inserted before ; The comparison times of words are the sum of the comparison times of each letter .

The number of comparisons of each letter in a word . It is the number of words included in the root node of this letter .

Word comparison functions such as the following ：

int strcmp(char *s, char *t)
{
    int i;
    for (i=0; s[i]==t[i]; i++)
        if (s[i]=='\0')
            return 0;
    return s[i] - t[i];
}

Copy

Because the comparison function is as above , Pay attention to the following points when calculating ：

1. The same length is L The cost of comparing two words of is 2L-1. Go out for the last time s Concluded inference ;

2. The comparative length of words should be strlen(str)+1, The terminator is also a part of comparison ;

3. Suppose two words are the same , Then calculate one more time to end the inference . Comparison times +1.

Be careful ： Use LL, Otherwise the data will overflow .

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long LL;

char words[1010];

/* Trie define */  
#define nodesize 4444444    // Number of nodes  
  
typedef struct node1  
{
	char    value;
	int     size;
	int     count;
    node1*  Lchild;
	node1*  Rchild;
}tnode;  
tnode dict[nodesize];
  
class Trie  
{  
    private:  
		LL     count;
        int    size;  
        tnode* root;
    public:  
        Trie() {initial();}   
        void initial() {  
            memset( dict, 0, sizeof(dict) );  
            size=0;count=0LL;root=newnode(0);
        }  
        tnode* newnode( char c ) {
			dict[size].value = c;
			return &dict[size ++];
		}  
        void insert( char* word, int L ) {  
            tnode* now = root->Rchild,*save = root; 
            int same = 1;
            for ( int i = 0 ; i <= L ; ++ i ) { 
				if ( !now ) {
					save->Rchild = newnode(word[i]);
					now = save->Rchild;
					now->count = 1;
					same = 0;
				}else {
					if ( i ) count += now->count;
					count += now->count ++;
					while ( now->Lchild && now->value != word[i] )
						now = now->Lchild;
					if ( now->value != word[i] ) {
						now->Lchild = newnode(word[i]); 
						now = now->Lchild;
						same = 0;
					}
				}
				save = now;
				now = save->Rchild;
            }
            if ( same ) save->size ++;
            count += save->size;
        }  
        LL query() {return count;}
}trie;  
/* Trie  end */  

int main()
{
	int Case = 1,N;
	while ( scanf("%d",&N) != EOF ) {
		if ( !N ) break;
		
		trie.initial();
		for ( int i = 0 ; i < N ; ++ i ) {
			scanf("%s",words);
			trie.insert(words,strlen(words));
		}
		
		printf("Case %d: %lld\n",Case ++,trie.query());
	}
	return 0;
}

Copy

Copyright notice ： This article is the original article of the blogger . Blog , Do not reprint without permission .

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116985.html Link to the original text ：https://javaforall.cn