Cod sursa(job #2449854)

Utilizator modulopaulModulopaul modulopaul Data 20 august 2019 21:34:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define minim(a, b) ((a < b) ? a : b)
#define MAXN 2000005

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[MAXN],b[MAXN];
int n,m;
int pi[MAXN],pos[1024];
void pref(){
    int q=0;
    pi[1]=0;
    for(int i=2;i<=m;i++){
        while(q and a[q+1]!=a[i])
            q=pi[q];
        if(a[q+1]==a[i])
            q++;
        pi[i]=q;
    }
}
int main(){
    int q=0,N=0;

    fin.get(a,MAXN);
    fin.get();
    fin.get(b,MAXN);
    for(; (a[m]>='A' and a[m]<='Z') || (a[m]>='a' and a[m]<='z') || (a[m]>='0' and a[m]<='9');m++);
    for(; (b[n]>='A' and b[n]<='Z') || (b[n]>='a' and b[n]<='z') || (b[n]>='0' and b[n]<='9');n++);
    for(int i=m;i!=0;i--)
        a[i]=a[i-1];
    a[0]=' ';
    for(int i=n;i;i--)
        b[i]=b[i-1];
    b[0]=' ';
    pref();
    for(int i=1;i<=n;i++){
        while(q and a[q+1]!=b[i])
            q=pi[q];
        if(a[q+1]==b[i])
            q++;
        if(q==m){
            q=pi[m];
            N++;
            if(N<=1000)
                pos[N]=i-m;
        }
    }
    fout<<N<<'\n';
    for(int i=1;i<=minim(N,1000);i++)
        fout<<pos[i]<<' ';
    return 0;
}