序列模式匹配

/*
暴力枚举应该也能通过，以下介绍一种动态规划算法
设dp[i][i+k]为text从i到i+k匹配到的pattern最长的长度
当text[i+k]==pattern[dp[i][i + k - 1]]时， dp[i][i + k] = dp[i][i + k - 1] + 1；
否则  dp[i][i + k] = dp[i][i + k - 1] 。
边界为 k=0时，dp[i][i] = (text[i] == pattern[0]);

因为要求最短匹配序列，所以k从0到n遍历；
又因为多个答案时输出起止位置最小的答案，所以i从0开始遍历。
此时第一个结果即为符合要求的答案
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1000

int main()
{
//    freopen("input.txt", "r", stdin);
    char text[N], pattern[N];
    while(cin >> text >> pattern) {
        int n = strlen(text), m = strlen(pattern);
        int dp[n][n];
        memset(dp, 0, sizeof(dp));
        bool flag = false;
        for(int k = 0; k < n; k++) {
            for(int i = 0; i + k < n; i++) {
                dp[i][i + k] = dp[i][max(i + k - 1, 0)] + (text[i + k] == pattern[dp[i][max(i + k - 1, 0)]]);
                if(dp[i][i + k] >= m) {
                    flag = true;
                    cout << i << " " << i + k << endl;
                }
                if(flag) break;
            }
            if(flag) break;
        }
        if(!flag) cout << "-1 -1" << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    while(cin>>a>>b)
    {
        int s=-1,e=-1,minn=1001;
         for(int i=0;i<=a.length()-b.length();i++)
         {
             if(a.find(b[b.length()-1],i+1)==a.npos||a.find(b[0],i)==a.npos)   break;
             int temp=a.find(b[0],i),flag=0;
             for(int j=1;j<b.length();j++)
             {
                 if(a.find(b[j],temp+1)!=a.npos)    
                     temp=a.find(b[j],temp+1);                 
                 else    {flag=1;break;}
             }
             int cnm=minn;
             if(!flag)    minn=min(minn,temp-(int)a.find(b[0],i));
             else break;
             if(minn!=cnm)    {e=temp;s=a.find(b[0],i);}
         }
        cout<<s<<" "<<e<<endl;  
    }
}

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

int main(){
    string s,t;
    while(cin>>s>>t){
        int n=s.length(), m=t.length(), a=-1, b=-1, l, r, Min=INT_MAX;
        for(int i=0,j=0;i<n;i++){
            if(s[i]==t[j]){
                if(j==0)
                    a = i;
                j++;
            }
            if(j==m){
                j = 0;
                b = i;
                if(b-a<Min){
                    Min = b - a;
                    l = a;
                    r = b;
                }
                i = a;
            }
        }
        if(b==-1)
            cout<<-1<<" "<<-1<<endl;
        else
            cout<<l<<" "<<r<<endl;
    }
    return 0;
}

测试用例有一个卡住了………………
题目要求的第一个字符串中含有的pattern串不用连续，所以很简单的就是遍历第一个字符串，以
一个下标来j取第二个字符串pattern串中的元素，如果相等，则j++即可，最后循环外判断一下j的
值。
#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        int j=0;
        vector<int> begin;
        for(int i=0;i<s1.size();i++)
        {
            if(j==s2.size())
                break;
            if(s1[i]==s2[j])
            {
                begin.push_back(i);
                j++;
            }
        }
        if(j==s2.size())
        {
            cout<<begin[0]<<' '<<begin[begin.size()-1]<<endl;
        }
        else{
            cout<<-1<<' '<<-1<<endl;
        }
    }
}

def match(s1, s2):
    if len(s1)<len(s2):return(-1,-1)
    i,j=0,0
    l,r,min_l = -1,-1,len(s1)+1
    while i<len(s1):
        if s1[i]==s2[j]:
            if j==len(s2)-1:
                k = i
                while(j>=0):
                    if s1[i]==s2[j]:
                        j-=1
                    i-=1
                i+=1
                temp_min = k-i+1
                if temp_min<min_l:
                    l,r,min_l = i,k,temp_min
            else:
                i+=1
                j+=1
        else:
            i+=1
    return (l,r)
while True:
    try:
        s1,s2 = input().split(' ')
        l,r = match(s1,s2)
        print(l,r)
    except:
        break

#include <iostream>
#include <string>
#include <climits>
using namespace std;
int main(){
    string s,t;
    while(cin>>s>>t){
        int n=s.size(),m=t.size(),a=-1,b=-1,l=-1,r=-1,min=INT_MAX;
        for (int i=0,j=0;i<n;i++){
            if (s[i]==t[j]){
                if (j==0)
                    a=i;
                j++;
            }
            if (j==m){
                b=i,j=0;
                if (b-a<min){
                    min=b-a;
                    l=a,r=b;
                }
                i=a;
            }
        }
        cout<<l<<" "<<r<<endl;
    }
}

import sys

def func(a, b):
    temp = {}
    i = 0
    j = 0
    start = -1
    end = -1
    
    while i < len(a):
        if a[i] == b[j]:
            j += 1
            
            if start == -1:
                start = i
                end = i
            else:
                end = i
            
            if j == len(b):
                if end - start not in temp:
                    temp[end-start] = [start, end]
                i = start
                j = 0
                start = -1
        i += 1
    if len(temp) > 0:
        res = temp[min(temp.keys())]
    else:
        res = [-1, -1]
    res_str = str(res[0]) + " " + str(res[1])
    print(res_str)


lines = sys.stdin.readlines()
for line in lines:
    text, pattern = line.strip().split()
    func(text, pattern)

动态规划是O(n^2)复杂度，暴力也是O(n^2)复杂度，干脆暴力了事。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String s = sc.next();
            String t = sc.next();

            int min = s.length() + 1;
            int start = -1;
            int end = -1;
            for(int i = 0; i < s.length(); i ++) {
                if(s.charAt(i) == t.charAt(0)) {
                    int k = 0;
                    int j = i;
                    while(j < s.length() && k < t.length()) {
                        if(s.charAt(j) == t.charAt(k)) {
                            k ++;
                        }

                        j ++;
                        if(j - i >= min) break;
                    }

                    if(k == t.length() && (j - i) < min) {
                        min = j - i;
                        start = i;
                        end = j - 1;
                    }
                }
            }

            System.out.println(start + " " + end);
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string text,pattern;
    while(cin>>text>>pattern)
    {
        int len1=text.size();
        int len2=pattern.size();
        int i=0,j,k,start;
        const int INF=0x3f3f3f3f;
        int minLen=INF;
        while(i<len1)//遍历text，只要遇到pattern[0]就开始匹配判断
        {
            if(text[i]==pattern[0]){
               j=0;
               for(k=i;k<len1;++k){//检测[i,len1)之间的字符是否能够完全匹配pattern
                   if(text[k]==pattern[j])//检查能够匹配到的pattern字符
                       j++;
                   if(j==len2){//找到了一个匹配,此时i指向text中第一个匹配pattern[0]的位置
                       if(minLen>k-i+1){
                          minLen=k-i+1;
                          start=i;
                       }
                       break;
                   }    
               }
            }
            ++i;
        }
        if(minLen==INF){
            cout<<"-1 -1"<<endl;
        }else{
            cout<<start<<" "<<start+minLen-1<<endl;
        }
    }
}

#include <iostream>
#include <string>
#include <tuple>
 
using namespace std;
 
tuple<int,int> getResult(const string& in,const string& s) {
    if(s.size() == 1) {
        auto f = in.find(s);
        if(f != string::npos)
            return make_tuple(f,f);
        else
            return make_tuple(-1,-1);
    }
    auto len = in.size();
    auto last = len - 1;
    auto min = 99999;
    auto left = -1,right = -1;
    for(int i = last; i >= 0; --i) {
        if(s[0] == in[i]) {
            auto p = 1;
            auto pos = -1;
            for(int j = i + 1;j <= len - 1; ++j) {
                if(s[p] == in[j]) {
                    ++p;
                    if(p == s.size()) {
                        pos = j;
                        break;
                    }
                }
            }
            
            if(pos != -1) {
                if(pos - i <= min) {
                    min = pos - i;
                    left = i;
                    right = pos;
                }
            }
            last = i;
        }
    }
    return make_tuple(left,right);
}
 
 
int main() {
    string input;
    while(cin>>input) {
        string toFind;
        cin>>toFind;
        auto res = getResult(input,toFind);
        cout<<std::get<0>(res)<<' ';
        cout << std::get<1>(res)<<'\n';
    }
    return 0;
}