Advertisement
zhora_15

Untitled

Nov 22nd, 2021
645
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.16 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. #define min(a, b) (((a) < (b)) ? (a) : (b))
  5.  
  6. void prefix(char s[], int p[]){
  7.     unsigned long long n = strlen(s);
  8.     for (unsigned int i = 1; i<n; ++i){
  9.         int j = p[i - 1];
  10.  
  11.         while (j > 0 && s[i] != s[j]) {
  12.             j = p[j - 1];
  13.         }
  14.  
  15.         if (s[i] == s[j]) {
  16.             p[i] = j + 1;
  17.         }
  18.         else {
  19.             p[i] = j;
  20.         }
  21.     }
  22. }
  23.  
  24. int main(void) {
  25.     char s1[1000001];
  26.     char s2[1000001];
  27.     char s[2000002];
  28.     int p[2000002] = {0};
  29.     //int p[20000] = {0};
  30.  
  31.     scanf("%1000000s", s1);
  32.     scanf("%1000000s", s2);
  33.  
  34.     strcpy(s, s1);
  35.     strcat(s, s2);
  36.     prefix(s, p);
  37.     if (p[strlen(s)-1] > min(strlen(s1), strlen(s2))){
  38.         printf("%lu ", min(strlen(s1), strlen(s2)));
  39.     }
  40.     else{
  41.         printf("%d ", p[strlen(s)-1]);
  42.     }
  43.  
  44.     strcpy(s, s2);
  45.     strcat(s, s1);
  46.     int p1[2000002] = {0};
  47.     //int p1[20000] = {0};
  48.     prefix(s, p1);
  49.     if (p1[strlen(s)-1] > min(strlen(s1), strlen(s2))){
  50.         printf("%lu", min(strlen(s1), strlen(s2)));
  51.     }
  52.     else{
  53.         printf("%d", p1[strlen(s)-1]);
  54.     }
  55.     return 0;
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement