首页 > 代码库 > POJ 1936 All in All 匹配, 水题 难度:0
POJ 1936 All in All 匹配, 水题 难度:0
题目
http://poj.org/problem?id=1936
题意
多组数据,每组数据有两个字符串A,B,求A是否是B的子串。(注意是子串,也就是不必在B中连续)
思路
设置计数器cnt为当前已匹配A的长度,明显在扫描B的过程中只需要记住cnt这一个状态。
扫描B,每次与A[cnt]匹配就将计数器增加1,cnt与A的长度一致时A就是B的子串。
感想
这道题也许可以用更复杂的方法。
代码
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <sstream> 6 using namespace std; 7 typedef long long ll; 8 const int maxn = 1e6 + 6; 9 int nxt[maxn]; 10 char pat[maxn]; 11 char maz[maxn]; 12 13 bool solve(){ 14 int cnt = 0; 15 for(int i = 0;maz[i];i++){ 16 if(maz[i] == pat[cnt])cnt++; 17 if(pat[cnt] == 0)return true; 18 } 19 return false; 20 } 21 22 int main(){ 23 #ifdef LOCAL 24 freopen("input.txt","r",stdin); 25 #endif // LOCAL 26 for(int i = 0;scanf("%s%s",pat,maz)==2;i++){ 27 bool ans = solve(); 28 if(ans){ 29 puts("Yes"); 30 }else{ 31 puts("No"); 32 } 33 } 34 35 return 0; 36 }
POJ 1936 All in All 匹配, 水题 难度:0
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。