Cod sursa(job #2931149)

Utilizator MrPuzzleDespa Fabian Stefan MrPuzzle Data 30 octombrie 2022 16:40:22
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<climits>
#include<iomanip>
#include<cstring>
#include<bitset>

#define MAX 2000000

using namespace std;

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

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

char s[MAX+5],pattern[MAX+5];
int n,m;
int i,j;

int ansk=0;
int ans[1005];

int patternNo[MAX+5];

int main(){

    f>>pattern+1;
    f>>s+1;

    n = strlen(pattern+1);
    m = strlen(s+1);

    i=2;j=1;
    ///setup pattern
    while(i<=n){
        if(pattern[j] == pattern[i]){

            patternNo[i] = j;
            i++;
            j++;

        }else if(j!=1){
            j=1;
        }else{
            i++;
        }
    }

    i=1;j=0;
    while(i<=m){

        if(j==n){
            ansk++;
            if(ansk<=1000){
                ans[ansk] = i-n-1;
            }

            j=patternNo[j];
        }else if(s[i] == pattern[j+1]){
            i++;
            j++;
        }else if(j!=0){
            j=patternNo[j];
        }else{
            i++;
        }
    }

    g<<ansk<<'\n';
    for(int i=1;i<=min(ansk,1000);i++){
        g<<ans[i]<<" ";
    }

    f.close();
    g.close();
    return 0;
}