Greedy+ prefix+suffix pattern matching | C++
Intuition\nWe calculate prefix and suffix arrays where prefix[i]=size of prefix of word2 that is in word1 upto word1[i], suffix[i]=size of suffix of word2 that 
# Intuition\nWe calculate prefix and suffix arrays where prefix[i]=size of prefix of word2 that is in word1 upto word1[i], suffix[i]=size of suffix of word2 that is in word1 upto word1[i]. Now if we are adding any index i in word1, it should satisfy that prefix[i-1]+1+suffix[i+1]>=m, i.e, we should get total string by adding this index, and characters matching in word2 before and after this index. We greedily choose first such index and construct the indices by moving through prefix array.\n\nOne edge case: word1[i] matches with word2[j] if we need to match j onwards after matching prefix[i-1]. Then we will greedily add next index till this match continues to get lexicographically smallest sequence of indices.\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> validSequence(string word1, string word2) {\n        int n=word1.size(),m=word2.size();\n        vector<int> suff(n+4),pref(n+4);\n        int j=0;\n        for(int i=0;i<n;++i){\n            if(j<m && word1[i]==word2[j]) j++;\n            pref[i+1]=j;\n        }\n        j=m-1;\n        for(int i=n-1;i>=0;--i){\n            if(j>=0 && word1[i]==word2[j]) j--;\n            suff[i+1]=m-j-1;\n        }\n        for(int i=0;i<n;++i){\n            if(pref[i]+suff[i+2]+1>=m){\n                vector<int> ans;\n                for(int t=1;t<=i;++t){\n                    if(pref[t]!=pref[t-1]) ans.push_back(t-1);\n                }\n                if(pref[i]<m) ans.push_back(i);\n                int cur=ans.size();\n                j=cur;\n\n                int t=i;\n                //edge case\n                while(j<m && j>0 && word1[t]==word2[j-1]){\n                    ans.push_back(t+1);\n                    t++;\n                    j++;\n                }\n                t++;\n                for(;t<n;++t){\n                    if(j<m && word1[t]==word2[j]){\n                        ans.push_back(t);\n                        j++;\n                    }\n                }\n                return ans;\n            }\n        }\n        return {};\n    }\n};\n```
['String', 'Greedy', 'C++']