Cod sursa(job #2458225)

Utilizator AnduebossAlexandru Ariton Andueboss Data 19 septembrie 2019 21:46:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
//
//  main.cpp
//  aVarcolaci
//
//  Created by Andu Andu on 19/09/2019.
//  Copyright © 2019 Andu Andu. All rights reserved.
//

#include <iostream>
#include <fstream>

using namespace std;

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

long long n;
 //char sir[100];
 //int numar[100];
long long i, j, kmp[4000001], x = -1;
long long sol[1001];
string a, b;
 int main() {
     f>>a>>b;
     string sir = a+"*"+b;
     long long n=sir.size();
     kmp[0] = -1;
     kmp[1] = 0;
     for(i=1;i<=n;i++) {
        // x=kmp[i-1];
     
         while(x>-1 && sir[x] != sir[i-1]) {
             x=kmp[x];
         }
         x++;
         kmp[i]=x;
         
     }
     long long s=a.size();
     long long nn=0;
     for(long long i=2*s;i<=n;++i) {
         
         if(kmp[i] == s) {
             if(nn<=1000) {
                 sol[nn]=i-2*s;
             }
             nn++;
         }
     }
     g<<nn<<"\n";
     for(i=0;i<min(nn, 1ll*1000);++i)
     {
         g<<sol[i]-1<<" ";
     }
     
     return 0;
 }