Pagini recente » Cod sursa (job #3001839) | Cod sursa (job #2823719) | Cod sursa (job #1187475) | Cod sursa (job #2380584) | Cod sursa (job #1170961)
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#define e '\n'
using namespace std;
//#define FILE "strmatch"
#define INF 1023456789
#define ll long long
#ifdef FILE
ifstream f(string (string(FILE) + ".in").c_str());
ofstream g(string (string(FILE) + ".out").c_str());
#endif
#ifndef FILE
#define f cin
#define g cout
#endif
string sach, needle;
vector<int> rez;
int pi[2000005];
int i, j, n, m, t;
int main() {
f >> needle;
f >> sach;
int pos = 0;
for (i=1; i<needle.size(); i++) {
while (needle[i] != needle[pos] && pos > 0) {
pos = pi[pos-1];
}
if (needle[i] == needle[pos]) {
pos++;
}
pi[i] = pos;
}
// for(i=0; i<needle.size(); i++) {
// g << pi[i] << " ";
// }
pos = 0;
for(i=0; i<sach.size(); i++) {
while (sach[i] != needle[pos] && pos > 0) {
pos = pi[pos-1];
}
if (sach[i] == needle[pos]) {
pos ++;
if (pos == needle.size()) {
rez.push_back(i - pos + 1);
pos = pi[pos-1];
}
}
}
g << rez.size() << e;
for (i=0; i<rez.size() && i<1000; i++) {
g << rez[i] << " ";
}
return 0;
}