Cod sursa(job #2961550)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 6 ianuarie 2023 17:45:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
#define ll long long
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAX 2000005
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector < int > raspuns;
string s1, s2;
int n, m, i, k, p[MAX+MAX];


int main()
{
    cin>>s1>>s2;
    n = s1.size();
    m = s2.size();

    if(n>m)
    {
        cout<<0;
        return 0;
    }

    s1 += '#';
    s1 += s2;

    p[0] = -1;
    for(int i=1;i<=n+m+1;++i)
    {
        k = p[i-1];
        while(k>=0 && s1[k] != s1[i-1])k = p[k];
        p[i] = k+1;

        if(p[i] == n)raspuns.pb(i-n-n-1);
    }
    cout<<raspuns.size()<<'\n';
    for(int i=0;i<min(1000,(int)raspuns.size());++i)
        cout<<raspuns[i]<<' ';
    return 0;
}