Cod sursa(job #2833679)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 15 ianuarie 2022 14:59:05
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include<fstream>
#include<cstring>
#include<vector>
#define N 2000001
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char str[N], pat[N];
int resume[N], n, m;
vector<int> res;
void BuildMatch(char *pat){
    resume[0] = 0;
    int i = 0, j = 1;
    while(j < m){
        if(pat[i] == pat[j]){
            resume[j] = i + 1;
            i++; j++;
        }
        else{
            if(i == 0)
                resume[j] = 0, j++;
            else 
                i = resume[i-1];
        }
    }
} 
int cnt = 0;
void Search(char *str, char *pat){
    BuildMatch(pat);
    int i = 0, // str
        j = 0; // pat
    while(i < n){
        //cout << i << " " << j << "\n";
        if(str[i] == pat[j]){
            i++, j++;
        }
        if(j == m){
            cnt++; 
            if(res.size() < 1000)res.push_back(i-j); // de unde incepe sirul potrivit
            j = resume[j-1];
        }
        else if(i<n && pat[j] != str[i]){
            if(j){
                j = resume[j-1];
            }
            else i++;
        }
    }
}
int main(){

    cin >> pat >> str;
    n = strlen(str);
    m = strlen(pat);
    
    //for(int i=0; i<m; i++) cout << resume[i] << " ";
    Search(str, pat);
    cout << cnt << "\n";
    for(int i=0; i<res.size(); i++)
        cout << res[i] << " ";
}