Cod sursa(job #2294268)

Utilizator refugiatBoni Daniel Stefan refugiat Data 2 decembrie 2018 08:55:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream si("strmatch.in");
ofstream so("strmatch.out");
int v[2000005];
int poz[1005];
int main()
{
    string a,b;
    si>>a>>b;
    int n=a.size();
    int m=b.size();
    int l=0;
    for(int i=1;i<n;) {
        if(a[i]==a[l]) {
            ++l;
            v[i]=l;
            ++i;
        }
        else
            if(l)
                l=v[l-1];
            else
                ++i;
    }
    int sol=0;
    l=0;
    for(int i=0;i<m;) {
        if(b[i]==a[l]) {
            ++i;
            ++l;
        }
        if(l==n) {
            if(sol<1000)
                poz[sol]=i-n;
            ++sol;
            l=v[l-1];
        }
        else {
            if(i<m&&b[i]!=a[l])
                if(l)
                    l=v[l-1];
                else
                    ++i;
        }
    }
    so<<sol<<'\n';
    sol=min(sol,1000);
    for(int i=0;i<sol;++i)
        so<<poz[i]<<' ';
    return 0;
}