牛客NOIP暑期七天营-普及组1-B相似度查询
相似度查询
https://ac.nowcoder.com/acm/contest/916/B
题目大意:给定一个母串,问从母串中最多依次抽出多少个字符恰好是另一个字符串的前缀?(m个匹配串)
对于每个要匹配的字符串,逐个字符查找,只有先找到前面的字符,后面的字符才能够匹配,因为要按照原来的顺序。
对于匹配成功的,母串前面那些字符就不能再用来匹配了,因为要按照原来顺序。(贪心:越先找到越好)
匹配数量就是匹配不成功的位置减1。
#include <stdio.h> int n, m, i, j, k; char a[5005], b[105]; int main(){ scanf("%d%d%s", &n, &m, a+1); while(m--){ scanf("%s", b+1); for(i=j=1; a[i]&&b[j]; i++){ if(a[i] == b[j]) j++; } printf("%d\n", j-1); } return 0; }