(2013-1)字符串匹配

问题描述:

对于主串M和模式串P,找到P在M中出现的所有子串的第一个字符在P中的位置。P中第一个字符所在的位置为0。首行的数字表示有多少组字符串。

样例输入:

输入:

2
ababababa
ababa
aaa
aa

输出:

0 2 4
0 1

思路:

从头在m中匹配p,找到匹配的第一个字符串pos,继续从pos+1开始下一次匹配

知识点:

string

  1. str.find(str1), 当str1是str的子串时,返回其在str中第一次出现的位置;如果不是,返回string::npos;
  2. string::npos本身值为1, 可以作为find函数失配时的返回值
  3. str.find(str1, pos)从pos位开始匹配str1,返回值与上面相同
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

void Solve(string m, string p){
    int pos = m.find(p);
    int len = m.size();
    printf("%d", pos);
    while(len - pos - 1 >= p.size()){    //如果剩余字符串的长度不小于p的长度则继续判断
        int pos1 = m.find(p, pos+1);
        if(pos1 != string::npos){
            printf(" %d", pos1);
            pos = pos1;
        }
        else
            break;
    }
    printf("\n");
}

int main(){
    string m, p;
    int n;
    scanf("%d%*c", &n);
    while(n--){
        getline(cin, m);
        getline(cin, p);
        Solve(m, p);
    }
    return 0;
}

 

上一篇:线段树求后继+环——cf1237D


下一篇:集合的复杂排序