如何解决这个匹配算法？

我们假设一个字母被换成另一个字母（M - > | V |，C - >（）我们不知道每个字母都会被转换（这意味着我们不知道（M - > | V | ...，C - >（）如果有两个字符串和最大数目被转换这种信并且不存在规则匹配如何解决这个匹配算法？

如果它是有界的，则结果为1，否则为0。

起初我的解决办法是这样的C源

#include<stdio.h> 
#include<string.h> 
#define MAXSTRING 100 

/** 
Test input 

2 
3 
mississippi 
nni55i55ippi 
2 
foobar 
|=o08ar 


**/ 

int main() { // declare main function 
    int test,t; // test number 
    int i,j; // input loop variant 
    int lv1, lv2, lv3; // loop variant 
    int lenString1, lenString2; // length of string 
    int maximum; // maximum value for LEET 
    char letter; // check letters 

    char c1, c2; 


    scanf("%d\n", &t); // take test case 


    for(test = 0; test < t ; test ++) { 
     char string1[MAXSTRING]={0,}, string2[MAXSTRING]={0,}; 
     int count1 = 0; 
     int result = 0; 
     int flipped = 0; 

     scanf("%d\n", &maximum); 
     for (i = 0; (c1 = getchar()) != '\n'; i++) { // make original string 
      string1[i] = c1; 
     } 
     for (j = 0; (c2 = getchar()) != '\n'; j++) { // make LEET string 
      string2[j] = c2; 
     }    
     lenString1 = strlen(string1); 
     lenString2 = strlen(string2); 

     if(lenString1 == 1 && string1[0] != string2[0]) { count1 = 1; } 
     else { 
     for (lv1 = 0; lv1 < lenString1; lv1++){ 
      for (lv2 = lv1; lv2 < lenString2 ; lv2++) { 
       if(string1[lv1+1] == string2[lv2] && string1[lv1] != string2[lv2-1]) { 
        letter = string2[lv2-1]; 
        for(lv3 = (lv1)+1; lv3 < lenString1; lv3++) { 
         if(string1[lv3] == string1[lv1] && string2[lv3] == letter) { flipped = 1; break;} 
         else { flipped = 0;} 
        } 
        count1++; 
        break; 
       } 
       if(flipped == 1) { break;} 
       else {flipped = 0;} 
      } 
     } 
     if(count1 > maximum) {result = 0;} 
     else {result = 1; } 
     } 
     printf("%d\n", count1); 
     printf("%d\n", result); 

    } 
    return 0; 

}

但它是行不通的。因为这种反例如果最大值是3，则这两种字符串。

ACMICPC - > 4（| V | I（|>（

我想是的count1 = 4，但它计数1.

如何解决这类问题？

来源

2011-11-20 Silvester

你的问题非常含糊......你的算法究竟在努力做什么？ ahhh是一个leet stringizer吗？ –

是的，但我们不知道leet stringfier的任何规则 – Silvester

好的，从我可以看的，你想创建leet字符串，使用一些标准的规则集。你可以在Wikipedia上找到一个列表。虽然如果您想在不知道任何约定的情况下将其反转，您只需创建每个字母的所有可能转换的列表，然后查找匹配项。 – darnir

您的代码正在对相等的字符进行计数，在您的反例中，您在两个字符串中都有单个I，因此count1为1。

在foobar示例中，您有A和R，count1 = 2。认为你在LEET版本中错误地输入了0，所以我不计算Os，对吧？）在密西西比州，你有我和P和count1 = 2.

虽然你并不遥远。你可以做的是计算相似的字符，并从原始字符串中的唯一字符数中减去该计数。这会给你转换字符的数量。

只是抬起头！我认为如果string1 [1] == string2 [0]，它会在第一次迭代（lv1 = lv2 = 0）时产生分段错误，因为它会查找string2 [-1]。

来源

2011-11-20 09:00:23

增加解决方案建议。 –

不，如果改变一次，count1 + 1 – Silvester

请您澄清一下吗？ –

如何解决这个匹配算法？

回答

相关问题