Cod sursa(job #3038598)

Utilizator PHOSSESSEDProsie Radu-Teodor PHOSSESSED Data 27 martie 2023 16:01:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

const int NMAX = 1e5 + 1;

char s[NMAX],t[NMAX]; int pi[NMAX];

void kmp()
{
    int n = strlen(s + 1),j = 0;
    for(int i = 2; i <= n ; i++)
        {
            while(j && s[i] != s[j + 1]) j = pi[j - 1];
            if(s[i] == s[j + 1]) j++;
            pi[i] = j;
        }
}

int main() {

    fin >> (s + 1) >> (t + 1); kmp();
    int j = 0; vector<int> ans;
    for(int i = 1; i <= strlen(t + 1) ; i++)
        {
            if(ans.size() >= 1000) break;
            while(j && t[i] != s[j + 1]) j = pi[j - 1];
            if(t[i] == s[j + 1]) j++;
            if(j == strlen(s + 1))
                {
                    ans.emplace_back(i - j);
                    j = pi[strlen(s + 1)];
                }
        }

    while(ans.size() > 1000) ans.pop_back();
    fout << ans.size() << '\n'; for(auto it : ans) fout << it << " ";
    return 0;
}