Cod sursa(job #3032314)

Utilizator Robilika2007Robert Badea Robilika2007 Data 21 martie 2023 22:09:45
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <vector>
#include <fstream>
#include <string.h>

using namespace std;

#define MAX_N 2000005

char v[MAX_N], sir[MAX_N];
int pi[MAX_N];

vector <int> ans;

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

int main()
{
    int x, i;

    in >> (v + 1);
    int n = strlen(v + 1);

    for(i = 2; i <= n; ++i)
    {
        x = pi[i-1];
        while(v[x + 1] != v[i] && x != 0)
            x = pi[x];

        if(v[x + 1] == v[i])
            pi[i] = x + 1;
        else
            pi[i] = 0;
    }


    in >> (sir + 1);
    int m = strlen(sir + 1);
    //while(cin >> sir[++m]);

    int j = 1;
    while(j <= m)
    {
        if(v[i] == sir[j])
        {
            if(i == n)
            {
                ans.push_back(j - i);
                j -= ( (pi[i] == i - 1) ? pi[i] - 1 : pi[i] );
                i = 1;
            } else
            {
                i++;
                j++;
            }
        } else
        {
            j -= ( (pi[i] == i - 1) ? pi[i] - 1 : pi[i] );
            i = 1;
        }
    }
    out << ans.size() << '\n';
    for(auto x : ans)
        out << x << " ";
    return 0;
}