匹配圆周率题 求助大神

寂寞知己

求助大神！   研究到哭  也是错误，网上搜不到~

jackz007

1. #include <stdio.h>
   
2. 
   
3. int match(char s1[] , char s2[])
   
4. {
   
5.         int i , j , m , n , r = -1                                             ;
   
6.         for(m = 0 ; s1[m] ; m ++)                                              ;
   
7.         for(n = 0 ; s2[n] ; n ++)                                              ;
   
8.         if(m >= n && n > 0) {
   
9.                 for(i = 0 ; i < m - n + 1 ; i ++) {
   
10.                         for(j = 0 ; j < n ; j ++) if(s1[i + j] != s2[j]) break ;
    
11.                         if(j == n) {
    
12.                                 r = i                                          ;
    
13.                                 break                                          ;
    
14.                         }
    
15.                 }
    
16.         }
    
17.         return r                                                               ;
    
18. }
    
19. 
    
20. int main(void)
    
21. {
    
22.         char s1[1000000] , s2[1000000]  ;
    
23.         scanf("%s" , s1)                ;
    
24.         scanf("%s" , s2)                ;
    
25.         printf("%d\n" , match(s1 , s2)) ;
    
26. }

复制代码

        编译、运行实况：

1. D:\00.Excise\C>g++ -o x x.c
   
2. 
   
3. D:\00.Excise\C>x
   
4. 1234
   
5. 1234
   
6. 0
   
7. 
   
8. D:\00.Excise\C>x
   
9. 1234
   
10. 12345
    
11. -1
    
12. 
    
13. D:\00.Excise\C>x
    
14. 821999052039574422
    
15. 19990520
    
16. 2
    
17. 
    
18. D:\00.Excise\C>x
    
19. 881994082555083527588321827035
    
20. 19940825
    
21. 2
    
22. 
    
23. D:\00.Excise\C>

复制代码

傻眼貓咪

1. #include <stdio.h>
   
2. 
   
3. int match(char A[], char B[]){
   
4.     for(int i = 0; A[i]; i++){
   
5.         if(A[i] == B[0]){
   
6.             int check = 1;
   
7.             for(int j = i, n = 0; B[n]; j++, n++){
   
8.                 if(B[n] != A[j]){
   
9.                     check = -1;
   
10.                     break;
    
11.                 }
    
12.             if(check) return i;
    
13.             }
    
14.         }
    
15.     }
    
16.     return -1;
    
17. }
    
18. 
    
19. int main(){
    
20.     char A[1000000], B[1000000];
    
21.     scanf("%s", A);
    
22.     scanf("%s", B);
    
23.     int answer = sizeof(A) >= sizeof(B) ? match(A, B) : -1;
    
24.     printf("%d", answer);
    
25. }

复制代码

100gram

寂寞知己

jackz007 发表于 2021-11-13 22:45
编译、运行实况：

最后的测试点显示超时，可能有些问题

寂寞知己

傻眼貓咪 发表于 2021-11-14 09:35

部分正确，有2个测试点不正确

傻眼貓咪

寂寞知己 发表于 2021-11-14 20:06
部分正确，有2个测试点不正确

已修改：

1. #include <stdio.h>
   
2. 
   
3. int match(char A[], char B[], int N, int M){
   
4.     for(int i = 0; i < N-M+1; i++){
   
5.         if(A[i] == B[0]){
   
6.             int check = 1;
   
7.             for(int j = i, n = 0; B[n]; j++, n++){
   
8.                 if(B[n] != A[j]){
   
9.                     check = -1;
   
10.                     break;
    
11.                 }
    
12.             if(check) return i;
    
13.             }
    
14.         }
    
15.     }
    
16.     return -1;
    
17. }
    
18. 
    
19. int main(){
    
20.     char A[1000000], B[1000000];
    
21.     scanf("%s", A);
    
22.     scanf("%s", B);
    
23.     int a, b;
    
24.     for(a = 0; A[a]; a++){}
    
25.     for(b = 0; B[b]; b++){}
    
26.     int answer = a > b ? match(A, B, a, b) : -1;
    
27.     printf("%d", answer);
    
28. }

复制代码

阿萨德按时

寂寞知己

傻眼貓咪 发表于 2021-11-14 20:57
已修改：

还是3个错误点。。。。。。

傻眼貓咪

寂寞知己 发表于 2021-11-15 21:08
还是3个错误点。。。。。。

抱歉，有没有可以参考的参数？

1molHF

寂寞知己

傻眼貓咪 发表于 2021-11-15 21:13
抱歉，有没有可以参考的参数？

只有这个。。。。。


第一个人是对的   只不过最后那个测试点显示超时，你这个借鉴下第一个人   把超时整没有了   应该就是正确答案啦

傻眼貓咪

寂寞知己

jackz007 发表于 2021-11-13 22:45
编译、运行实况：

这个超时能解决一下吗？

jackz007

寂寞知己 发表于 2021-11-15 22:17
这个超时能解决一下吗？

        那就再试试这个？

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         char s1[1000000] , s2[1000000]                                         ;
   
6.         int i , j , k = -1 , m , n                                             ;
   
7.         scanf("%s" , s1)                                                       ;
   
8.         scanf("%s" , s2)                                                       ;
   
9.         for(m = 0 ; s1[m] ; m ++)                                              ;
   
10.         for(n = 0 ; s2[n] ; n ++)                                              ;
    
11.         if(m >= n && n > 0) {
    
12.                 for(i = 0 ; i < m - n + 1 ; i ++) {
    
13.                         for(j = 0 ; j < n ; j ++) if(s1[i + j] != s2[j]) break ;
    
14.                         if(j == n) {
    
15.                                 k = i                                          ;
    
16.                                 break                                          ;
    
17.                         }
    
18.                 }
    
19.         }               
    
20.         printf("%d\n" , k)                                                     ;
    
21. }

复制代码

寂寞知己

jackz007 发表于 2021-11-15 22:49
那就再试试这个？

还是超时。。。。。。。。。。。。。。

jackz007

寂寞知己 发表于 2021-11-15 22:51
还是超时。。。。。。。。。。。。。。

            这个呢？

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         char c , s1[1000000] , s2[1000000]                                     ;
   
6.         int i , j , k = -1 , m , n                                             ;
   
7.         for(m = 0 ; (c = getchar()) != '\n' ; m ++) s1[m] = c                  ;
   
8.         for(n = 0 ; (c = getchar()) != '\n' ; n ++) s2[n] = c                  ;
   
9.         if(m >= n && n > 0) {
   
10.                 for(i = 0 ; i < m - n + 1 ; i ++) {
    
11.                         for(j = 0 ; j < n ; j ++) if(s1[i + j] != s2[j]) break ;
    
12.                         if(j == n) {
    
13.                                 k = i                                          ;
    
14.                                 break                                          ;
    
15.                         }
    
16.                 }
    
17.         }               
    
18.         printf("%d\n" , k)                                                     ;
    
19. }

复制代码

寂寞知己

jackz007 发表于 2021-11-15 22:59
这个呢？

还是超时。。。。。。。。       最后那个检测点超时 ，应该还是算法出了问题，有某处跟题不符合吧。。

傻眼貓咪

寂寞知己 发表于 2021-11-15 23:02
还是超时。。。。。。。。       最后那个检测点超时 ，应该还是算法出了问题，有某处跟题不符合吧。。

这已经是我的极限了，希望不会错：

1. #include <stdio.h>
   
2. 
   
3. int kmp(char S[], char W[], int s, int w){
   
4.     int P[s], nP = 0, j = 0, k = 0, T[s];
   
5.     for(int i = 0; i < s; i++){
   
6.         T[i] = -1;
   
7.         P[i] = -1;
   
8.     }
   
9.     while(j < s){
   
10.         if(W[k] == S[j]){
    
11.             j++;
    
12.             k++;
    
13.             if(k == w){
    
14.                 P[nP] = j-k;
    
15.                 nP++;
    
16.                 k = T[k];
    
17.             }
    
18.         }
    
19.         else{
    
20.             k = T[k];
    
21.             if(k < 0){
    
22.                 j++;
    
23.                 k++;
    
24.             }
    
25.         }
    
26.     }
    
27.     for(int i = 0;; i++){
    
28.         if(P[i] > 0){
    
29.             return P[i];
    
30.         }
    
31.     }
    
32. }
    
33. 
    
34. int main()
    
35. {
    
36.     char A[1000000], B[1000000];
    
37.     scanf("%s", A);
    
38.     scanf("%s", B);
    
39.     int a, b;
    
40.     for(a = 0; A[a]; a++){}
    
41.     for(b = 0; B[b]; b++){}
    
42.     int answer = a > b ? kmp(A, B, a, b) : -1;
    
43.     printf("%d", answer);
    
44. }

复制代码

jackz007

寂寞知己 发表于 2021-11-15 23:02
还是超时。。。。。。。。       最后那个检测点超时 ，应该还是算法出了问题，有某处跟题不符合吧。。

        题目要求使用 KMP 快速模式匹配，我在网上抄了一段代码，现在再试试呢

1. #include <stdio.h>
   
2. 
   
3. void Next(char * T , int * next)
   
4. {
   
5.         int i = 1 , j = 0 , m                        ;
   
6.         next[1] = 0                                  ;
   
7.         for(m = 0 ; T[m] ; m ++)                     ;
   
8.         while(i < m) {
   
9.                 if(j == 0 || T[i - 1] == T[j - 1]) {
   
10.                         i ++                         ;
    
11.                         j ++                         ;
    
12.                         next[i] = j                  ;
    
13.                 } else {
    
14.                         j = next[j]                  ;
    
15.                 }
    
16.         }
    
17. }
    
18. 
    
19. int KMP(char * S , char * T)
    
20. {
    
21.         int i = 1 , j = 1 , next[10] , m , n         ;
    
22.         for(m = 0 ; S[m] ; m ++)                     ;
    
23.         for(n = 0 ; T[n] ; n ++)                     ;
    
24.         Next(T , next)                               ;
    
25.         while(i <= m && j <= n) {
    
26.                 if (j == 0 || S[i - 1] == T[j - 1]){
    
27.                         i ++                         ;
    
28.                         j ++                         ;
    
29.                 } else {
    
30.                         j = next[j]                  ;
    
31.                 }
    
32.         }
    
33.         if(j > n) return i - n - 1                   ;
    
34.         else return -1                               ;
    
35. }
    
36. 
    
37. int main(void)
    
38. {
    
39.         char c , s1[1000000] , s2[1000000]                   ;
    
40.         int m , n                                            ;
    
41.         for(m = 0 ; (c = getchar()) != '\n'; m ++) s1[m] = c ;
    
42.         for(n = 0 ; (c = getchar()) != '\n'; n ++) s2[n] = c ;
    
43.         s1[m] = s2[n] = '\0'                                 ;
    
44.         printf("%d\n" , KMP(s1, s2))                         ;
    
45. }

复制代码