Promi_38

pattern matching

Jan 9th, 2021
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. /*In this problem I will give you an array A of length n and an array B of length m. You have to count how many sub-array are there in A which is equal to B
  2.  
  3. Input Format
  4.  
  5. First line will contain two number n and m which indicate the length of the array.
  6.  
  7. Second line will contain n number Ai.
  8.  
  9. Third line will contain m number Bi.
  10.  
  11. Output Format
  12.  
  13. In a single line print the answer of the question.
  14.  
  15. Sample Input 0
  16.  
  17. 7 2
  18. 1 2 1 2 3 2 1
  19. 1 2
  20. Sample Output 0
  21.  
  22. 2
  23. Explanation 0
  24.  
  25. Here, =[1,2,1,2,3,2,1] and =[1,2]
  26.  
  27. Here all the subarray of  is [1],[1,2],[1,2,1],[1,2,1,2],[1,2,1,2,3],[1,2,1,2,3,2],[1,2,1,2,3,2,1],[2],[2,1],[2,1,2],[2,1,2,3],[2,1,2,3,2],[2,1,2,3,2,1],[1],[1,2],[1,2,3],[1,2,3,2],[1,2,3,2,1],[2],[2,3],[2,3,2],[2,3,2,1],[3],[3,2],[3,2,1],[2],[2,1],[1]
  28.  
  29. so number of subarray which is equal to  is 2 */
  30.  
  31. #include<stdio.h>
  32.  
  33. int main()
  34. {
  35.     long long n, m;
  36.     scanf("%lld %lld", &n, &m);
  37.    
  38.     long long a[n], b[m], x, i, j, cnt, ans = 0;
  39.     for(i = 0; i < n; i++) scanf("%lld", &a[i]);
  40.     for(i = 0; i < m; i++) scanf("%lld", &b[i]);
  41.    
  42.     for(i = 0; i < n; i++)
  43.     {
  44.         x = i, cnt = 0;
  45.         for(j = 0; j < m; )
  46.         {
  47.             if(a[x] == b[j])
  48.             {
  49.                 cnt++, j++, x++;
  50.             }
  51.             else break;
  52.             if(cnt == m)
  53.             {
  54.                 ans++;
  55.                 break;
  56.             }
  57.         }
  58.     }
  59.     printf("%lld\n", ans);
  60. }
Advertisement
Add Comment
Please, Sign In to add comment