c中字符串字符的唯一性

Question

有没有有效、简单的方法来检查c中字符串字符的唯一性？在我的情况下，我必须检查用户输入的ISBN是否具有唯一字符，并且长度为13个字符。

Answer 1

假设字符串只有13个字节，暴力方法似乎足够快，甚至比更复杂的方法更快，而且更容易编写和验证检查。

这里有一个例子：

#include <ctype.h>
#include <stdio.h>
#include <string.h>
int check_ISBN(const char *p) {
if (strlen(p) != 13)
return -1;
while (*p) {
unsigned char c = *p++;
// characters must be digits or lowercase letters
if (!isdigit(c) && !islower(c))
return 2;
// characters must not be duplicated
if (strchr(p, c))
return 1;
}
return 0;
}
int main(int argc, char *argv[]) {
int status = 0;
if (argc < 2) {
fprintf(stderr, "Usage: %s ISBN ...n", argv[0]);
return 2;
}
for (int i = 1; i < argc; i++) {
switch (check_ISBN(argv[i])) {
case 0:
printf("%s: valid ISBN.n", argv[i]);
break;
case 1:
printf("%s: invalid ISBN: duplicate digit.n", argv[i]);
status = 1;
break;
case 2:
printf("%s: invalid ISBN: invalid character.n", argv[i]);
status = 1;
break;
default:
printf("%s: invalid ISBN: bad character count.n", argv[i]);
status = 1;
break;
}
}
return status;
}

Answer 2

只需对字符串进行迭代，将每个看到的字符记录在查找表中。如果看到重复，请中止。如果长度不是13，则失败。例如：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <libgen.h>
#include <limits.h>
int
validate(const char *a, char **err)
{
char lut[(1 << CHAR_BIT)] = {0};  /* 256 */
int len = 0;
*err = "too short";
for(const char *s = a; *s; s += 1 ){
if( ++len > 13 ){
*err = "too long";
return 0;
}
if( lut[(unsigned char)*s] ){
*err = "duplicate entry";
return 0;
}
lut[(unsigned char)*s] = 1;
}
return len == 13;
}

int
main(int argc, char **argv)
{
int fail = 0;
if( argc == 1 ){
printf("usage: %s isbn [isbn...]n", basename(argv[0]));
return 0;
}
for( argv += 1; *argv; argv += 1 ){
char *e;
if( ! validate(*argv, &e) ){
fprintf(stderr, "%s is invalid: %sn", *argv, e);
fail += 1;
}
else {
printf("%s is validn", *argv);
}
}
return fail == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
}

Answer 3

要添加到@WilliamPursell答案，这里有一种使用位掩码而不是字符数组查找表的方法：

#include <stdio.h>
// Check if this is a ISBN and its 13 digits uniqueness.
// Parameters:
//    ISBN, ASCIIZ
// Returns: [int]
//     -1 :  Not a ISBN
//      0 :  ISBN with only unique digits
//      1 :  ISBN with duplicated digits
int isISBNDigitsUnique(char *pStr) {
if (pStr == NULL) return -1;
unsigned long long mask = 0, refmask; 
unsigned char bit;
int expected_length = 0, ret = 0;    
while((bit = *pStr++) && expected_length++ < 14) {
if (bit < '0' || bit > '9' && bit < 'A') return -1;
if ((bit &= 0xDFu) > 'Z') return -1;
if (ret==0) {
refmask = mask; 
if ((bit -= 0x10u) > 0x30u) bit -= 0x20u; 
if ((mask |= (0x01u << bit)) == refmask) ret = 1;
}
}
if (expected_length != 13) return -1;
return ret;
}
int main(int nbargs, char *args[]) {
if (nbargs != 2) {
printf("Usage : %s ISBNn", args[0]);
return 1;
}
switch (isISBNDigitsUnique(args[1])) {
case 1:
printf("duplicate digit!n");
break;
case 0:
printf("all digits are unique.n");
break;
default:
printf("%s is not an ISBN.n", args[1]);
}
}

应用于每个数字的布尔逻辑：

我们认为0-9、a-z和a-z是ISBN的唯一有效数字。由于我们有一个用于ISBN的ASCIIZ缓冲区，我们可以预期每个数字以下是数字ASCII码的二进制值。

0011 0000到0011 1001＝>数字0-90100 0001至0101 1010＝>数字A-Z0110 0001至0111 1010＝>数字a-z

我们首先检查数字是否满足以下要求：

• 如果数字代码低于48，则它不是有效数字
• 如果数字代码大于57且小于65，则它不是有效的数字

我们通过将第7位归零来应用大小写减少，因此使用0xDF的AND掩码。我们有以下数字的值范围：

0001 0000至0001 1001＝>数字0-90100 0001至0101 1010＝>数字A-Z0100 0001至0101 1010＝>数字a-z

如果数字代码大于90，则它不是有效数字。

我们将0x10减去数字代码，目标是为每个值拟合一个64位掩码。我们有以下数字的值范围：

0000 0000到0000 1001=>数字0-9，十进制值0-90011 0001至0100 1010＝>数字A-Z，十进制值49-740011 0001至0100 1010＝>数字a-z，十进制值49-74

我们可以将第6位归零，因为第5位足以区分0-9和a-z，但由于我们的结果范围将超过64，如果数字代码大于48，则减去0x20更有效。我们有以下数字的值范围：

0000 0000到0000 1001 0-9=>数字0-9，十进制值0-90001 0001至0010 1010 A-Z＝>数字A-Z，十进制值17-420001 0001至0010 1010 a-z＝>数字a-z，十进制值17-42

我们的数字代码值范围现在是0-9和17-42，这很容易适应64位掩码。所以我们只需要为每个数字标记每个位，如果数字代码没有改变掩码，那么我们就有一个重复的数字。

附言：@interjay对于数学方法，我希望检查数字总和和数字乘积，但这需要数学演示。。。。