Cod sursa(job #2588386)

Utilizator whothefuckareunicu buliga whothefuckareu Data 24 martie 2020 18:55:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>

using namespace std;
#define ll unsigned long long
#define INF 1234567890
#define N (int)(2e6 + 5)
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int ps[N];
int ras[1001];
int main()
{
    string patt, s;
    fin >> patt >> s;
    int nr = 0;
    int n = patt.length(), m = s.length();
    int i = 0, j = 1;
    while(j < n)
    {
        if(patt[i] == patt[j]) ps[j] = i + 1, i++, j++;else
            if(!i) ++j;else i = ps[i - 1];
    }
    i = 0, j = 0;
    while(i < m)
    {
        if(s[i] == patt[j]) i++, j++;else
            if(!j) ++i;else j = ps[j - 1];
            if(j == n - 1 && s[i] == patt[j]) ras[++nr] = i - n + 1;
    }
    fout << nr << "\n";
    for(int i = 1; i <= min(1000, nr); ++i)
        fout << ras[i] << " ";
    return 0;
}