Intuitive and clean solution using suffix subsequent match array and greedy
Intuition\n Describe your first thoughts on how to solve this problem. \nUse a suffix array to track the max suffix length of word2 can be matched from a given 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse a suffix array to track the max suffix length of word2 can be matched from a given position in word1, and then attempts to find the best positions to perform the required operation.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAfter the suffix array is built, simply loop through each position in word1 to greedily calculate the best position to apply operation and get the answer.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    vector<int> validSequence(string word1, string word2) {\n        int n = word1.length(), m = word2.length();\n        vector<int> suffix(word1.length());\n        vector<int> empt;\n        for (int i = n - 1; i >= 0; i--) {\n            if (i == n - 1) {\n                suffix[i] = word1[n-1] == word2[m-1] ? 1 : 0;\n            } else {\n                suffix[i] = suffix[i + 1];\n                if (suffix[i + 1] < m &&\n                    word1[i] == word2[m - suffix[i + 1] - 1]) {\n                    suffix[i] = suffix[i + 1] + 1;\n                }\n            }\n        }\n        vector<int> ans;\n        int j = 0;\n        int op=1; \n        for (int i = 0; i < n && j < m; i++) {\n            if (word1[i] == word2[j]) {\n                j++;\n                ans.push_back(i);\n            } else {\n                int left = m - j;\n                if (i + 1 < n && (left <= suffix[i + 1] + 1) && op==1) {\n                    op--;\n                    ans.push_back(i);\n                    j++;\n                }\n            }\n        }\n        if(ans.size()==m)\n            return ans;\n        return empt;\n    }\n};\n```
['Greedy', 'Suffix Array', 'C++']