Cod sursa(job #2432861)

Utilizator cyg_Alex_codegicianBarbu Alexandru cyg_Alex_codegician Data 25 iunie 2019 12:24:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int k;
void creare_lps(char a[],int m,int lps[])
{
    int i=1,len;
    lps[0]=len=0;
    while (i<m)
    {
        if (a[i]==a[len])
        {
            len++;
            lps[i]=len;
            i++;
        }
        else
        {
            if (len!=0)
            {
                len=lps[len-1];
            }
            else
            {
                lps[i]=0;
                i++;
            }
        }
    }
}
void kmp(char a[],int m,char b[],int n,int lps[],int poz[])
{
    int i=0,j=0;
    while (i<n)
    {
        if (b[i]==a[j])
        {
            i++;
            j++;
            if (j==m)
            {
                poz[k++]=i-m;
                if (k>999) break;
                j=lps[j-1];
            }
        }
        else
        {
            if (j!=0) j=lps[j-1];
            else i++;
        }
    }
}
int main()
{
    char a[2000005],b[2000005];
    int lps[2000005],poz[1005];
    cin.getline(a,2000005);
    cin.getline(b,2000005);
    int m=strlen(a),n=strlen(b);
    creare_lps(a,m,lps);
    kmp(a,m,b,n,lps,poz);
    cout << k << '\n';
    for (int i=0;i<k;i++)
    {
        cout << poz[i]  << " ";
    }
}