Cod sursa(job #2266827)

Utilizator vadim171098vadim pislari vadim171098 Data 22 octombrie 2018 21:48:48
Problema Potrivirea sirurilor Scor 8
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

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

int getz(string P, int z[],int len)
{
    int n = P.length();
    int sum =0;
    z[1] = 0;
    int l = 0, r = 0;
    for (int i = 2; i <= n; ++i) {
        if (i <= r) {
            z[i] = min(z[i - l + 1], r - i + 1);
        }

        while (i + z[i] - 1 <= n  &&  P[i + z[i]] == P[z[i] + 1]) {
            ++z[i];
        }

        if (i + z[i] - 1 >= r) {
            r = i + z[i] -1;
            l = i;
        }
    if(z[i] == len)sum++;
    }
    return sum;
}

void str(string text, string sch)
{
    string imp = sch + "#" + text;
    int l = imp.length(),len =sch.length();

    int Z[l];
    int dim = getz(imp, Z,len);
    out<<dim<<endl;
    for (int i = 0; i < l; ++i)
    {
        if (Z[i] == sch.length())
            out << i - len -1 << " ";
    }
}


int main()
{
    string sch,text;
    in>>sch>>text;
    str(text, sch);
    return 0;
}