不満な文字列 \(T\) は \(S_1, S_2, \dots, S_N\) のいずれかと一致することから、不満な文字列があるとすれば \(S_1, S_2, \dots, S_N\) の中に存在します。
したがって、 \(S_1, S_2, \dots, S_N\) の各 \(S\) について、 !\({}+S\) が \(S_1, S_2, \dots, S_N\) の中に含まれるかを調べれば良いです。
これは、 HashSet (unordered_set) などを用いることによって、効率的に判定できます。

回答例 (C++)

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<string> S(N);
    for(string& s : S) cin >> s;
    unordered_set<string> h(S.begin(), S.end());
    for(string& s : S) if(h.count('!' + s)){
        cout << s << endl;
        return 0;
    }
    cout << "satisfiable" << endl;
}

回答例 (Python)

N = int(input())
S = set(input() for i in range(N))
for s in S:
    if "!" + s in S:
        print(s)
        exit()
print("satisfiable")