Cod sursa(job #2700931)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 29 ianuarie 2021 12:30:38
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define NMAX 2000002

using namespace std;

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

char A[NMAX], B[NMAX];
int lps[NMAX],cnt;

vector<int>rasp;

int main()
{
    in.getline(A,NMAX);
    in.getline(B,NMAX);
    int n=strlen(A), m=strlen(B);
    if(n>m)
    {
        out<<'0';
        return 0;
    }
    lps[0]=0;
    int l=0;
    for(int i=1;i<n;i++)
    {
        if(A[l]==A[i])
            lps[i]=++l;
        else
        {
            if(l==0)
                lps[i]=0;
            else
            {
                l=lps[l-1];
                i--;
            }
        }
    }
    int i=0,j=0;
    while(i<m)
    {
        if(A[j]==B[i])
        {
            i++;
            j++;
        }
        else
        {
            if(j==n)
            {
                cnt++;
                if(cnt<=1000)
                    rasp.push_back(i-n);
            }
            if(j==0)
                i++;
            else
                j=lps[j-1];
        }
    }
    out<<cnt<<'\n';
    for(int i=0;i<1000 && i<cnt;i++)
        out<<rasp[i]<<' ';
    return 0;
}