Pagini recente » Cod sursa (job #210875) | Cod sursa (job #1606054) | Cod sursa (job #1451698) | Cod sursa (job #116321) | Cod sursa (job #1983341)
#include <iostream>
#include <fstream>
#include <string>
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define PI 3.141592653589793;
using namespace std;
int lps[4000005];
int result[1002];
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
f>>a>>b;
int ind = 0, i = 1, j = 0, n = a.size(), m = b.size(), nr = 0;
while(i < n){
if(a[i] == a[ind]){
lps[i] = ind + 1;
i++;
ind++;
} else if(ind){
ind = lps[ind - 1];
} else {
i++;
}
}
i = 0;
while(i < m){
if(b[i] == a[j]) {
i++;
j++;
} else if(j){
j = lps[j - 1];
} else {
i++;
}
if(j == a.size()){
nr++;
j = lps[j-1];
if(nr <= 1000)
result[nr] = i - n;
}
}
g<<nr<<'\n';
for(int i=1; i <= min(nr, 1000); i++)
g<<result[i]<<' ';
}