Cod sursa(job #2600240)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 12 aprilie 2020 12:36:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <string>
using namespace std;
 
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
 
string s, w;
 
//folosim algoritmul KMP -> https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
int t[2000001], n, m;
//t[i] = lungimea celui mai lung prefix al lui w, astfel incat acesta sa fie sufix al lui a[0...i]; t[i] != i (adica nu pot avea prefix = sufix)
 
void precalc()
{
    int i, k = 0;
    t[0] = -1;
    for (i = 1; i<w.size(); i++, k++)
    {
        if (w[k] == w[i])
            t[i] = t[k];
        else
        {
            t[i] = k;
            while (k >= 0 && w[i] != w[k])
                k = t[k];
        }
    }
    t[w.size()] = k;
}
 
int ap[1001];
 
int main()
{
    fin >> w >> s;
    precalc();
    int i, k = -1;
    for (i = 0; i<s.size(); i++)
    {
        while (k >= 0 && w[k] != s[i])
            k = t[k];
        if (k < 0)
            k = 0;
        if (w[k] == s[i])
        {
            k++;
            if (k == w.size())
            {
                ap[0]++;
                if (ap[0] <= 1000)
                    ap[ap[0]] = i-k+1;
                k = t[k];
            }
        }
    }
    fout << ap[0] << '\n';
    for (i = 1; i<=min(ap[0], 1000); i++)
        fout << ap[i] << ' ';
    return 0;
}