week16- A2. Apple Pen Hard, Author Solution

#include<bits/stdc++.h>
using namespace std;
const int SIZE = 1000001;
string s[SIZE];
int pre[SIZE],suf[SIZE];
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    string T;
    cin>>T;
    for(int i=1;i<=n;i++){
        if(s[i].size()>T.size())continue;
        for(int j=0;j<s[i].size();j++){
            if(s[i][j]!=T[j])break;
            if(j+1==s[i].size())pre[j]=i;
        }
        for(int j=0;j<s[i].size();j++){
            if(s[i][j]!=T[T.size()-s[i].size()+j])break;
            if(j+1==s[i].size())suf[T.size()-s[i].size()]=i;
        }
    }
    vector<pair<int,int> >an;
    for(int i=1;i<T.size();i++){
        if(pre[i-1]&&suf[i]&&pre[i-1]!=suf[i]){
            an.push_back(make_pair(pre[i-1],suf[i]));
            if(an.back().first>an.back().second)
                swap(an.back().first,an.back().second);
        }
    }
    sort(an.begin(),an.end());
    an.resize(unique(an.begin(),an.end())-an.begin());
    printf("%d\n",(int)an.size());
    for(int i=0;i<an.size();i++)printf("%d %d\n",an[i].first,an[i].second);
}