Cod sursa(job #2653542)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 28 septembrie 2020 14:48:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

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

string s;
string a, b;

unsigned int p[4000000 + 7];

int main()
{
    in >> a >> b; //s = '*' + a + '*' + b;
    s.resize(2 + a.size() + b.size());

    s[0] = '*';
    for(int i = 1; i <= a.size(); i++)
        s[i] = a[i-1];
    s[a.size()+1] = '*';
    for(int i = a.size()+2; i < s.size(); i++)
        s[i] = b[i - a.size() - 2];

    //cout << s << endl;

    unsigned int k = 0;
    for(unsigned int i = 2; i < s.size(); i++)
    {
        while(k > 0 && s[k+1] != s[i])
            k = p[k];
        if(s[k+1] == s[i])
            k++;
        p[i] = k;
    }

    int nr_ap = 0;
    for(unsigned int i = 0; i < s.size(); i++)
    {
        //cout << p[i] << endl;

        if(p[i] == a.size())
            nr_ap++;
    }

    out << nr_ap << endl;
    if(nr_ap > 1000) nr_ap = 1000;
    for(unsigned int i = 0; i < s.size(); i++)
    {
        if(p[i] == a.size() && nr_ap--)
            out << i - 1 - 2*a.size() << " ";
    }
}