Cod sursa(job #2859805)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 1 martie 2022 22:41:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int kmp[4000004];
vector<int> place;

int main()
{
    string s, t;
    fin>>s>>t;
    t = " " + s + t;
    s = " " + s;
    int n = t.size() - 1;
    int k = 0;
    kmp[1] = 0;
    for (int i = 2; i <= n; i++)
    {
        while (k > 0 && t[k + 1] != t[i])
        {
            k = kmp[k];
        }
        if (t[k + 1] == t[i]) k++;
        kmp[i] = k;
    }
    int ap = 0;
    k = 0;
    for(int i = s.size();i < t.size(); i++)
    {
        while(k && s[k+1] != t[i])
            k = kmp[k];
        if(s[k+1] == t[i])
            k++;
        if(k == s.size() - 1)
        {
            ap++;
            if (ap <= 1000)
                place.push_back(i);
        }
    }
    fout<<ap<<"\n";
    for (auto a : place)
    {
        fout<<a - 2 * (s.size() - 1)<<" ";
    }
    return 0;
}