如何解決這個匹配算法？

我們假設一個字母被換成另一個字母（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

請您澄清一下嗎？ –

如何解決這個匹配算法？

回答

相關問題