Cod sursa(job #2210755)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 7 iunie 2018 20:39:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

const int NMAX = 2000005;
string target, s;
int kmp[NMAX];

int main() {
    cin >> target;
    cin >> s;
    target = " " + target;
    s = " " + s;
    int k = 0;
    for(int i = 2; i < target.size(); i ++) {
        while(k > 0 && target[k + 1] != target[i])
            k = kmp[k];
        if(target[k + 1] == target[i])
            k ++;
        kmp[i] = k;
    }
    k = 0;
    vector<int> sol;
    for(int i = 1; i < s.size(); i ++) {
        while(k > 0 && target[k + 1] != s[i])
                k = kmp[k];
        if(target[k + 1] == s[i])
            k ++;
        if(k == target.size() - 1) {
                k = kmp[k];
                if(sol.size() <= 1000)
                    sol.push_back(i - (target.size() - 1));
        }
    }
    cout << sol.size() << "\n";
    for(int i = 0; i < sol.size(); i ++)
        cout << sol[i] << " ";
    return 0;
}