Cod sursa(job #3243782)

Utilizator Ayan__bAyan Bozesan Ayan__b Data 21 septembrie 2024 11:34:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <iostream>
#define NMAX 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int z[NMAX], N;
void strmatch(string str) {
    N = str.length();
    long l, r;
    l = r = 0;
    for (long i = 1; i < N; ++i) {
        if (i > r) {
            long j = 0;
            r = l = i;
            while (r < N && str[j] == str[r]) {
                j++;
                r++;
            }
            r--;
            z[i] = r - l + 1;
        }
        else {
            long k = i - l;
            if (z[k] < r - i) {
                z[i] = z[k];
            }
            else {
                long j = r - i;
                l = i;
                while (r < N && str[j] == str[r]) {
                    j++;
                    r++;
                }
                r--;
                z[i] = r - l + 1;
            }
        }
    }
}
int main()
{
    string word, s;
    f >> word >> s;
    long len = word.length(), con = 0, nr = 0;
    strmatch(word + "?" + s);
    for (long i = len; i < N; ++i) {
        if (z[i] == len) {
            con++;
        }
    }
    g << con << "\n";
    for (long i = len; i < N; ++i) {
        if (z[i] == len) {
            g << i - len - 1 << " ";
            nr++;
        }
        if (nr >= 1000)
            break;
    }
    return 0;
}