首页 > 代码库 > Vijos1425子串清除 题解
Vijos1425子串清除 题解
Vijos1425子串清除 题解
描述：
我们定义字符串A是字符串B的子串当且仅当我们能在B串中找到A串。现在给你一个字符串A，和另外一个字符串B，要你每次从B串中从左至右找第一个A串，并从B串中删除它，直到A串不为B串的子串，问你需要进行几次删除操作。
输入格式：
输入文件共2行，第一行一个字符串A（长度小于256），第二行一个字符串B。
30%的数据是随机生成的；
50%的数据满足输入文件大小小于300KB；
100%的数据满足输入文件小于500KB，字符串A、B中只会出现英文字母。
输出格式：
输出文件只有一个整数N。
样例：
abc
abcabcabaabcbccc
样例说明:
abcabcabaabcbccc-> abcabaabcbccc-> abaabcbccc-> ababccc-> abcc
分析：
刚开始看到这题时，立刻想到了KMP+双向链表的写法，但是由于代码实现比较复杂，就放弃了这个想法。
一位大神告诉我们可以用栈模拟匹配的操作，每次将元素压入栈中，看栈顶元素是否与子串匹配，如下图所示：
例如：
子串：abc
母串：abcababcc 。
第一步：
先将a入栈，不匹配；
将b入栈，不匹配；
将c入栈，匹配，并弹出栈顶相应元素，ans++ 。
第二步：
将a入栈，不匹配；
将b入栈，不匹配；
将a入栈，不匹配；
将b入栈，不匹配；
将c入栈，匹配,ans++,弹出相应元素；
第三步：
将c入栈，匹配,ans++,弹出相应元素；
以上就是用栈模拟的过程，下面代码：
1 #include "iostream" 2 #include "cmath" 3 #include "cstdio" 4 #include "cstring" 5 #define maxN 10000010 6 7 using namespace std ; 8 char a[maxN], b[maxN], stack[maxN]; 9 int Lena, Lenb;10 11 bool match ( int top )//匹配函数12 {13 14 for(int i = top, j = Lena ; i >= 1 && j >= 1 ; --i, --j)15 {16 if(a[j] != stack[i])return false ;17 }18 19 return true ;20 21 }22 23 int main ( )24 {25 long long ans = 0 ;26 scanf("%s%s", a + 1, b + 1);27 Lena = strlen(a + 1);28 Lenb = strlen(b + 1);29 int top = 1 ;30 for(int i = 1 ; i <= Lenb ; ++i )31 {32 stack[top] = b[i];33 if(stack[top] == a[Lena] && top >= Lena && match(top))34 {35 ans++;36 top -= Lena;37 }38 top++;39 }40 printf("%I64d", ans);41 return 0 ;42 }
（完）
Vijos1425子串清除 题解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。