搬运我的洛谷题解，原文创作时间：2026-03-19 22:32。

思路：

这道题由于字符串长度太长了，所以不能用简单的 find 函数，需要使用 KMP 算法。

KMP 算法是一种高效的字符串匹配算法，可以利用已经匹配好的信息，来避免主串的指针回溯。这样时间复杂度就会降低，变成 $O(n+m)$。

先要把字符串 $l$ 的 $A$ 与 $T$， $G$ 与 $C$，一对一交换配对，最后用 KMP 进行匹配即可。

代码：

#include<bits/stdc++.h> 
using namespace std;
int main(){
    string l,s;
    cin>>l>>s;
    string t="";
    for(char ch:s){
        if(ch=='A') t+='T';
        else if(ch=='T') t+='A';
        else if(ch=='G') t+='C';
        else if(ch=='C') t+='G';
    }
    vector<int>next(s.size());
    for(int i=1,j=0;i<s.size();i++){
        while(j&&t[i]!=t[j]){
            j=next[j-1];
        }
        if(t[i]==t[j]){
            j++;
        }
        next[i]=j;
    }
    for(int i=0,j=0;i<l.size();i++){
        while(j&&l[i]!=t[j]){
            j=next[j-1];
        }
        if(l[i]==t[j]){
            j++;
        }
        if(j==s.size()){
            cout<<i-s.size()+2;
            return 0;
        }
    }
    cout<<0;
	return 0; 
}