codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

625B.md (2192B)


      1 Source: https://codeforces.com/problemset/problem/625/B
      2 
      3 B. War of the Corporations
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A long time ago, in a galaxy far far away two giant IT-corporations Pineapple and Gogol continue their fierce competition. Crucial moment is just around the corner: Gogol is ready to release it's new tablet Lastus 3000.
     22 
     23 This new device is equipped with specially designed artificial intelligence (AI). Employees of Pineapple did their best to postpone the release of Lastus 3000 as long as possible. Finally, they found out, that the name of the new artificial intelligence is similar to the name of the phone, that Pineapple released 200 years ago. As all rights on its name belong to Pineapple, they stand on changing the name of Gogol's artificial intelligence.
     24 
     25 Pineapple insists, that the name of their phone occurs in the name of AI as a substring. Because the name of technology was already printed on all devices, the Gogol's director decided to replace some characters in AI name with "#". As this operation is pretty expensive, you should find the minimum number of characters to replace with "#", such that the name of AI doesn't contain the name of the phone as a substring.
     26 
     27 Substring is a continuous subsequence of a string.
     28 
     29 Input
     30 
     31 The first line of the input contains the name of AI designed by Gogol, its length doesn't exceed 100 000 characters. Second line contains the name of the phone released by Pineapple 200 years ago, its length doesn't exceed 30. Both string are non-empty and consist of only small English letters.
     32 
     33 Output
     34 
     35 Print the minimum number of characters that must be replaced with "#" in order to obtain that the name of the phone doesn't occur in the name of AI as a substring.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 intellect  
     43 tell
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 1
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 google  
     56 apple
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 0
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 sirisiri  
     69 sir
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 2
     76 ```
     77 
     78 Note
     79 
     80 In the first sample AI's name may be replaced with "int#llect".
     81 
     82 In the second sample Gogol can just keep things as they are.
     83 
     84 In the third sample one of the new possible names of AI may be "s#ris#ri".