Pagini recente » Cod sursa (job #2829304) | Cod sursa (job #2835663) | Cod sursa (job #3137758) | Cod sursa (job #1525707) | Cod sursa (job #2465465)
//
// main.cpp
// ZAlgorithm
//
// Created by Andu Andu on 30/09/2019.
// Copyright © 2019 Andu Andu. All rights reserved.
//
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmach.out");
void getZarray(string str, int Z[]) {
int n = str.length();
int L, R, k;
L=R=0;
for(int i=1;i<n;i++) {
if (i > R) {
L=R=i;
while ( R<n && str[R-L] == str[R]) {
R++;
}
Z[i] = R-L;
R--;
} else {
k = i-L;
if(Z[k] < R-i+1) {
Z[i] = Z[k];
} else {
L = i;
while ( R<n && str[R-L] == str[R]) {
R++;
}
Z[i] = R-L;
R--;
}
}
}
}
vector<int> indexes;
void searchFor(string text, string pattern) {
string concat = pattern + "$" + text;
int l = concat.length();
int Z[l];
getZarray(concat, Z);
for ( int i=0;i<l;i++) {
if (Z[i] == pattern.length()) {
//cout<<"pattern at index: "<< i-pattern.length() - 1<<"\n";
indexes.push_back(i-pattern.length() - 1);
}
}
}
int main() {
string text;// = "CABBCABABAB";
string pattern;// = "ABA";
cin>>pattern>>text;
searchFor(text, pattern);
cout<<indexes.size()<<"\n";
for(int i=0;i<=indexes.size() - 1;i++) {
cout<<indexes[i]<<" ";
}
return 0;
}