Consider how to determine if \(S_i\) can be equal to \(T\), i.e. with \(T \coloneqq S_i\), one of the four conditions in the problem statement may hold. The original problem can be solved by judging this for each \(I\).

Let \(T \coloneqq S_i\). Inspect \(T\) and \(T'\) from the beginning to count how many initial characters of them coincide; let \(A\) be the maximum length of coinciding prefix. Also, let \(B\) be the maximum length of coinciding suffix. For example, if we have abcd and abcdacd, the first three characters abc coincide, and so do the last two characters cd.

Then, the four conditions can be rephrased as follows, where \(|T|\) and \(|T'|\) denotes the lengths of \(T\) and \(T'\), respectively:

• \(T'\) equals \(T\): \(A = B = |T| = |T'|\)
• \(T'\) is obtained by inserting a lowercase English letter to a position of \(T\) (possibly at the beginning or at the end): \(A+B \geq |T| = |T'|-1\)
• \(T'\) is obtained by removing one character from \(T\): \(A+ B \geq |T|-1 = |T'|\)
• \(T\) is obtained by replacing one character of \(T\) with another lowercase English letter: \(A +B = |T| -1 = |T'| - 1\)

Therefore, it is sufficient to actually check if \(A, B, |T|\), and \(|T'|\) satisfy one of the four conditions above.

The following is sample code in C++ language.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

ll n;
string s[500001], t2;
ll a[500001], b[500001];

ll calc(const string &s, const string &t)
{
  for(int i = 0; i < (int)t.size(); i++){
    if(i >= s.size()) return s.size();
    if(s[i] != t[i]) return i;
  }
  return t.size();
}

int main(void){
  cin >> n >> t2;
  for(int i = 1; i <= n; i++) cin >> s[i];

  for(int i = 1; i <= n; i++) a[i] = calc(s[i], t2);
  reverse(t2.begin(), t2.end());
  for(int i = 1; i <= n; i++){
    reverse(s[i].begin(), s[i].end());
    b[i] = calc(s[i], t2);
  }
  
  vector<ll> ans;
  for(int i = 1; i <= n; i++){
    const string &t = s[i];
    bool flag = false;
    if(a[i] == t.size() && t.size() == t2.size()) flag = true;
    if(a[i]+b[i] >= t.size() && t.size()+1 == t2.size()) flag = true;
    if(a[i]+b[i] >= t.size()-1 && t.size()-1 == t2.size()) flag = true;
    if(a[i]+b[i] == t.size()-1 && t.size() == t2.size()) flag = true;
    if(flag) ans.push_back(i);
  }
  
  cout << ans.size() << endl;
  for(auto x : ans) cout << x << " ";
  cout << endl;
  
  return 0;
}