Cod sursa(job #2782850)

Utilizator alien14Razvan alien14 Data 13 octombrie 2021 11:30:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>
using namespace std;
#define dim 2000001
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char a[dim],b[dim];
int v[1001],p[dim];
int k,t;

int main() 
{
    ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);
    fin>>a;
    fin>>b;
    int m = strlen(a);
    int n = strlen(b);
    for(int i = 2;i<m;++i)
    {
        while(k && a[k+1] != a[i])
            k = p[k];
        if(a[k+1] == a[i])
            k++;
        p[i] = k;
    }
    int i;
    for(k = 0,i=1;i<n;i++) 
    {
        while(k && a[k+1] != b[i])
            k=p[k];
        if(a[k+1] == b[i])
            k++;
        if(k == m-1 && a[0] == b[i-k])
        {
            if(t < 1000)
                v[t] = i-m+1;
            t++;
        }
    }
    for(fout<<t<<'\n', t=t>1000?1000:t, i=0;i<t;++i)
        fout<<v[i]<<" ";
    fin.close();
    fout.close();
    return 0;
}