Pagini recente » Cod sursa (job #1634678) | Cod sursa (job #1918179) | Cod sursa (job #743273) | Cod sursa (job #458759) | Cod sursa (job #2465474)
//
// main.cpp
// ZAlgorithm
//
// Created by Andu Andu on 30/09/2019.
// Copyright © 2019 Andu Andu. All rights reserved.
//
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
void getZarray(string str, ll Z[]) {
ll n = str.length();
ll L, R, k;
L=R=0;
for(ll 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<ll> indexes;
void searchFor(string text, string pattern) {
string concat = pattern + "$" + text;
ll l = concat.length();
ll Z[l];
getZarray(concat, Z);
for ( ll 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";
ll len;
if (indexes.size() - 1 > 1000) {
len = 1000;
} else {
len = indexes.size() - 1;
}
for(ll i=0;i<=len;i++) {
cout<<indexes[i]<<" ";
}
return 0;
}