Cod sursa(job #3226668)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 22 aprilie 2024 14:39:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

#define cin fin
#define cout fout

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

const int NMAX=2e6+5;

string a;
string b;

vector<int>v[NMAX];
int p[NMAX];

void kmp(int n)
{
    int i,k=0;
    for(i=1;i<n;i++)
    {
        while(a[i]!=a[k] && k>0)
            k=p[k-1];
        if(a[i]==a[k])
            k++;
        p[i]=k;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,i,j,m;
    vector<int>v;
    cin>>a>>b;
    n=a.size();
    m=b.size();
    kmp(n);
    int k=0;
    for(i=0;i<m;i++)
    {
        while(b[i]!=a[k] && k>0)
            k=p[k-1];
        if(b[i]==a[k])
            k++;
        if(k==n)
            v.push_back(i-n+1);
    }
    cout<<v.size()<<"\n";
    int debuff=0;
    for(auto i:v)
    {
        debuff++;
        cout<<i<<" ";
        if(debuff==1000)
            break;
    }
    return 0;
}