Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- Md. Shahidul Islam (shahidul_brur)
- Begum Rokeya University, Rangpur
- */
- #include<bits/stdc++.h>
- using namespace std;
- const int MAX = 100005;
- int pi[MAX];
- void prefix(string sub)
- {
- int m=sub.length();
- pi[0] = -1;
- for(int i=1, now=0;i<m;i++, now++){
- while(now>=0 && sub[i]!=sub[now])
- now = pi[now];
- pi[i] = now;
- }
- }
- int kmp(string str, string sub)
- {
- int n=str.length();
- int m=sub.length();
- prefix(sub);
- for(int i=0, now=0;i<n;i++){
- while(now>=0 && str[i]!=sub[now])
- now = pi[now];
- now++;
- if(now==m) return 1;
- }
- return 0;
- }
- int main()
- {
- int test, f;
- string s1, s2;
- while(cin>>s1>>s2)
- {
- if(kmp(s1, s2)==1) cout << "Yes\n";
- else cout << "No\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement