题解：CF1968B Prefiquence

lailai0916 · 2024-05-04 15:23:15 · 题解

题意简述

求字符串 a 的最长前缀是字符串 b 的子序列。

解题思路

枚举字符串 b。如果等于 a_i，说明目前长度为 i 的前缀符合要求，后续判断长度为 i+1 的前缀是否符合要求，所以令 i\gets i+1。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        string a,b;
        cin>>n>>m>>a>>b;
        int i=0,j=0;
        while(i<n&&j<m)
        {
            if(a[i]==b[j])i++;
            j++;
        }
        cout<<i<<'\n';
    }
    return 0;
}